Polymorphic max heap in Haskell

Question

The following example is my attempt at solving "take N most frequent words" in Haskell.

I'd like to make heap function to work for both String and Text. It works for any of those, but not both as a is 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)

What is the underlying problem?

{-# 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" ]

Actually it's even more a duplicate of http://stackoverflow.com/q/34398326/190376. — Reid Barton, Jan 23 '16 at 18:41
@ReidBarton I re-opened it to close with the new question you pointed out. But SO is not showing me the option to close now. :/ — Sibi, Jan 23 '16 at 19:29
There's also the [canonical MR question](http://stackoverflow.com/q/32496864/791604). — Daniel Wagner, Jan 23 '16 at 23:59

score 2 · Accepted Answer · answered Jan 23 '16 at 20:55

What is the underlying problem?

The monomorphism restriction. That restriction is making Haskell type frequencyDesc as MultiSet String instead of as forall a. (IsString a) => MultiSet a.

If you explicitly turn off the restriction, the result compiles:

{-# 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" ]

Also, with the restriction on, but with more explicit type signatures (so that Haskell doesn't trigger the restriction) you can get it to compile:

{-# 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" ]

Polymorphic max heap in Haskell

1 Answers1