[Haskell-cafe] Markov chain algorithm (from "The Practice of Programming", Kernighan/Pike)

[Daniel Fischer]

On Wednesday 11 May 2011 17:39:39, michael rice wrote:
> It's hard to improve on a 20 line Awk program for generating text but I
> thought it would be fun to investigate a Haskell solution. Why can't I
> cons an element onto an existing list?
> Michael
> Prelude Data.List Data.Map> insertWith (:) ("Moby", "Dick") "will"
> (fromList [(("Joe", "Blow"),["is"]), (("Moby", "Dick"),["may"])])
> <interactive>:1:11:    Occurs check: cannot construct the infinite
> type: a = [a]      Expected type: a      Inferred type: [a]    In the
> first argument of `insertWith', namely `(:)'    In the expression:     
>   insertWith          (:)          ("Moby", "Dick")          "will"   
>       (fromList [(("Joe", "Blow"), ["is"]), (("Moby", "Dick"),
> ["may"])])Prelude Data.List Data.Map>

The type of insertWith is

insertWith :: Ord k =>
     (a -> a -> a) -> k -> a -> Data.Map.Map k a -> Data.Map.Map k a

, so the combining function takes arguments of the same type, while

(:) :: a -> [a] -> [a]

Trying to use that for insertWith leads to the constraint a = [a], which 
gives rise to an infinite type error. (What would happen if the key is not 
yet in the Map, there's no way to pick a default value in general).

Use `insertWith (++) key [value]' instead, or Data.Map.alter.