[Haskell-cafe] Recursion problem in infinite list model

Miguel Mitrofanov miguelimo38 at yandex.ru
Thu Mar 27 10:58:34 EDT 2008


Hmmm, seems like your (-+) is not lazy enough.

Since pattern matching is strict by default, you have

anything -+ (_|_) = (_|_)

Therefore, the function, which is constantly (_|_), is a fixed point  
for the equation defining h. In other words, if you define

h' x = undefined

then you have

h' x = (-+) anything (h anything)

in particular,

h' x = (-+) (first x) (h (rest x))

You can fix it by defining (-+) as

x -+ ~(List y) = ...

> 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))
> --------
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



More information about the Haskell-Cafe mailing list