# [Haskell-cafe] Recursion problem in infinite list model

Claude Heiland-Allen claudiusmaximus at goto10.org
Thu Mar 27 10:18:00 EDT 2008

```Hans Aberg wrote:
> 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))

The combination of (-+) and h is too strict, this modification works:

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

Claude
--
http://claudiusmaximus.goto10.org
```