[Haskell-cafe] Recursion problem in infinite list model

[Claude Heiland-Allen]

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