[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 can isolate the problem with the addition in the code below, where  
I have defined a type Natural just in order to introduce a user  
defined operator. - For ordinals, it is more complicated. Then
   h (list 6)
only printouts "[N 6,", after which it gets stuck in the Natural.+.  
Adding ~ to
   (N x) + (N y)
does not help, nor other variations. But replacing Natural with  
integer, produces the normal infinite list printout. So it must be  
here it is stuck.

   Hans


--------
infix 5  :+

data Natural = N Integer
   deriving (Eq, Show)

instance Num Natural where
   fromInteger x = N x
   abs x = x
   signum 0 = 0
   signum _ = 1
   (N x) + (N y) = N(x + y)


data List a = (Natural->a) :+ Natural

instance Show a => Show (List a) where
   show (f :+ _) = "[" ++ show (f(0)) ++
     concat ["," ++ show (f(N (toInteger i)))| i<-[1..]] ++ "]"

list :: Natural -> List Natural
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))
--------