Type error in generator , haskell list using tuple

Question

Currently working with Haskell on a function that takes a String in parameters and return a list of (Char, Int) The function occur works with multiple type and is used in the function called word.

occur::Eq a=>a->[a]->Int
occur n [] = 0
occur n (x:xs) = if n == x
              then 1 + occur n xs
              else occur n xs

word::String->[(String,Int)]
word xs = [(x,y) | x<-head xs, y<-(occur x xs)]

Get me this error

ERROR "file.hs":31 - Type error in generator
*** Term           : head xs
*** Type           : Char
*** Does not match : [a]

What am I doing wrong ? How can I make this code run properly , type-wise ?

bheklilr bheklilr · Accepted Answer · 2014-01-23T21:06:42

The problem is you say that xs has type String, so head xs has type Char, and then you try to iterate over a single Char, which can't be done. The a <- b syntax only works when b is a list. You have the same problem in that y <- occur x xs is trying to iterate over a single Int, not a list of Int. You also had a problem in your type signature, the first type in the tuple should be Char, not String. You can fix it with:

word :: String -> [(Char, Int)]
word xs = [(x, occur x xs) | x <- xs]

Here we loop over the entire string xs, and for each character x in xs we compute occur x xs.

I would actually recommend using a slightly stronger constraint than just Eq. If you generalize word (that I've renamed to occurrences) and constrain it with Ord, you can use group and sort, which allow you to keep from iterating over the list repeatedly for each character and avoid the O(n^2) complexity. You can also simplify the definition pretty significantly:

import Control.Arrow
import Data.List

occurrences :: Ord a => [a] -> [(a, Int)]
occurrences = map (head &&& length) . group . sort

What this does is first sort your list, then group by identical elements. So "Hello, world" turns into

> sort "Hello, world"
" ,Hdellloorw"
> group $ sort "Hello, world"
[" ", ",", "H", "d", "e", "lll", "oo", "r", "w"]

Then we use the arrow operator &&& which takes two functions, applies a single input to both, then return the results as a tuple. So head &&& length is the same as saying

\x -> (head x, length x)

and we map this over our sorted, grouped list:

> map (head &&& length) $ group $ sort "Hello, world"
[(' ',1),(',',1),('H',1),('d',1),('e',1),('l',3),('o',2),('r',1),('w',1)]

This eliminates repeats, you aren't having to scan the list over and over counting the number of elements, and it can be defined in a single line in the pointfree style, which is nice. However, it does not preserve order. If you need to preserve order, I would then use sortBy and the handy function comparing from Data.Ord (but we lose a nice point free form):

import Control.Arrow
import Data.List
import Data.Ord (comparing)

occurrences :: Ord a => [a] -> [(a, Int)]
occurrences = map (head &&& length) . group . sort

occurrences' :: Ord a => [a] -> [(a, Int)]
occurrences' xs = sortBy (comparing ((`elemIndex` xs) . fst)) $ occurrences xs

You can almost read this as plain English. This sorts by comparing the index in xs of the first element of the tuples in occurrences xs. Even though elemIndex returns a value of type Maybe Int, we can still compare those directly (Nothing is "less than" any Just value). It simply looks up the first index of each letter in the original string and sorts by that index. That way

> occurrences' "Hello, world"

returns

[('H',1),('e',1),('l',3),('o',2),(',',1),(' ',1),('w',1),('r',1),('d',1)]

with all the letters in the original order, up to repetition.

Type error in generator , haskell list using tuple

1 Answers