[Haskell-cafe] Recursion problem in infinite list model

Hans Aberg haberg at math.su.se
Thu Mar 27 09:40:11 EDT 2008

When experimenting with list index sets (i.e. lists more general than  
provided by Haskell), I arrived at the problem that in the example  
code below for example
   h(list 6)
does not (in Hugs) write out the beginning of the list lazily. It  
does work for
   list 6
   first (list 6)
   rest (list 6)
   10 -+ (list 3)
and so on. So it seems to be a problem with h, also suggested by heap  
profiling, perhaps similar to that of "foldl".

So is it possible to fix it? The function h x is derived by unwinding  
the monadic construct corresponding to (for lists)
   do {i <- [x..]; return i}
So there are not many possibilities of change.

Below, (-+) corresponds, for lists, to ":", "first" to "head", and  
"rest" to "tail".

   Hans Aberg

data List a = List(Integer->a)

instance Show a => Show (List a) where
   show (List f) = "[" ++ show (f(0)) ++
     concat ["," ++ show (f(toInteger i))| i<-[1..]] ++ "]"

list :: Integer -> List Integer
list x = List(\z -> x+z)

(-+) :: a -> List a -> List a
x -+ (List y) = List(f) where
   f 0 = x
   f k = y(k-1)

first :: List a -> a
first (List f) = f 0

rest :: List a -> List a
rest (List y) = List(f) where
   f k = y(k+1)

h :: List a -> List a
h x = (-+) (first x) (h (rest x))

More information about the Haskell-Cafe mailing list