Haskell 中的多态最大堆

Question

下面的例子是我在Haskell中解决"take N most frequent words"的尝试。

我想让 heap 函数同时适用于 String 和 Text。它适用于其中任何一个，但不适用于两者，因为 a 是 "rigid type variable"。

   Couldn't match type ‘a’ with ‘String’
      ‘a’ is a rigid type variable bound by
          the type signature for heap :: H.Heap H.FstMaxPolicy (Occur, a)

根本问题是什么？

{-# LANGUAGE OverloadedStrings, ExplicitForAll #-}

module Main where

import Data.MultiSet as M
import Data.String
import Data.Tuple as T
import Data.Text(Text)
import qualified Data.Text as T
import qualified Data.Heap as H

main = undefined
solution = H.take 3 heap
heap :: forall a. H.Heap H.FstMaxPolicy (Occur, a)
-- heap = foldr H.insert H.empty heapItems
heap = undefined
heapItems = fmap T.swap list
list = toOccurList frequencyDesc
frequencyDesc = foldr M.insert M.empty myWords
myWords :: forall a. (IsString a) => [a]
myWords = [ "a", "b", "a", "b", "c" ]

Answer 1

What is the underlying problem?

单态限制。该限制使 Haskell 键入 frequencyDesc 作为 MultiSet String 而不是 forall a. (IsString a) => MultiSet a.

如果您明确关闭限制，结果编译：

{-# LANGUAGE OverloadedStrings, ExplicitForAll, NoMonomorphismRestriction #-}

module Main where

import Data.MultiSet as M
import Data.String
import Data.Tuple as T
import Data.Text(Text)
import qualified Data.Text as T
import qualified Data.Heap as H

main = undefined
solution = H.take 3 heap
heap :: forall a. (Ord a, IsString a) => H.Heap H.FstMaxPolicy (Occur, a)
heap = foldr H.insert H.empty heapItems
-- heap = undefined
heapItems = fmap T.swap list
list = toOccurList frequencyDesc
frequencyDesc = foldr M.insert M.empty myWords
myWords :: forall a. (IsString a) => [a]
myWords = [ "a", "b", "a", "b", "c" ]

此外，有了限制，但有了更明确的类型签名（这样 Haskell 就不会触发限制），您可以编译它：

{-# LANGUAGE OverloadedStrings, ExplicitForAll #-}

module Main where

import Data.MultiSet as M
import Data.String
import Data.Tuple as T
import Data.Text(Text)
import qualified Data.Text as T
import qualified Data.Heap as H

main = undefined
solution = H.take 3 heap
heap :: forall a. (Ord a, IsString a) => H.Heap H.FstMaxPolicy (Occur, a)
heap = foldr H.insert H.empty heapItems
-- heap = undefined
heapItems :: forall a. (Ord a, IsString a) => [(Occur, a)]
heapItems = fmap T.swap list
list :: forall a. (Ord a, IsString a) => [(a, Occur)]
list = toOccurList frequencyDesc
frequencyDesc :: forall a. (Ord a, IsString a) => MultiSet a
frequencyDesc = foldr M.insert M.empty myWords
myWords :: forall a. (IsString a) => [a]
myWords = [ "a", "b", "a", "b", "c" ]

Haskell 中的多态最大堆

Polymorphic max heap in Haskell

heap

haskell