[Haskell-cafe] Recursion problem in infinite list model

[Hans Aberg]

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))
--------