[Haskell-cafe] Recursion problem in infinite list model
Hans Aberg
haberg at math.su.se
Fri Mar 28 06:07:14 EDT 2008
On 28 Mar 2008, at 03:03, Ryan Ingram wrote:
> Another way to defer the evaluation of the second argument of (-+)
> is like this:
>
> (-+) :: a -> List a -> List a
> x -+ y = List(f) where
> f 0 = x
> f k = case y of List g -> g (k-1)
>
> This is exactly what the lazy pattern will do at compile-time. Does
> this give you a better understanding of how lazy patterns work and why
> they fix the problem?
>
I have various other patterns that need to be forced lazy - inputs
welcome. In the code below, where I have put in a "0" instead of the
first uncountable ordinal w, if I include in "show" the case a == 0,
then
h (list 6)
won't print, as then the value of "a" is computed.
And in the ordinal version
data List a = (Ordinal->a) :+ Ordinal
then the function
(-+) :: a -> List a -> List a
x -+ ~(y :+ q) = f:+(1+q) where
f 0 = x
f k = y(k-1)
does not compute, because there is a similar problem with the 1+q
evaluation, I think this is because the class Ordinal + uses case:
instance Num Ordinal where
x + y | finite x && finite y = toOrdinal(tcoef x + tcoef y)
x + y | lexp x < lexp y = y
x + y | lexp x == lexp y = prepend (lexp x, lcoef x + lcoef y)
(trail y)
x + y = prepend (lexp x, lcoef x) ((trail x) + y)
So these patterns perhaps should be made lazy. though I do not know
exactly how.
Hans
--------
infixr 5 :+
data List a = (Integer->a) :+ Integer
instance Show a => Show (List a) where
-- show (f:+a) | a == 0 = "[]"
show (f :+ a) = "[" ++ show (f(0)) ++
concat ["," ++ show (f(toInteger i))| i<-[1..]] ++ "]"
list :: Integer -> List Integer
list x = (\z -> x+z) :+ 0
(-+) :: a -> List a -> List a
x -+ ~(y :+ q) = f:+(1+q) where
f 0 = x
f k = y(k-1)
first :: List a -> a
first (f :+ _) = f 0
rest :: List a -> List a
rest (y :+ _) = f :+ 0 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