[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
More information about the Haskell-Cafe
mailing list