Talk:Y combinator: Difference between revisions
Content added Content deleted
(→Haskell stateless?: Recursive types?) |
|||
Line 9: | Line 9: | ||
Hi Spoon, The task does not rule out recursive types (I didn't know what they were at the time of writing) - just recursive functions. --[[User:Paddy3118|Paddy3118]] 11:05, 28 February 2009 (UTC) |
Hi Spoon, The task does not rule out recursive types (I didn't know what they were at the time of writing) - just recursive functions. --[[User:Paddy3118|Paddy3118]] 11:05, 28 February 2009 (UTC) |
||
It's not immediatly clear what is meant by the term "stateless," but let's assume it means something like "definable System F." (most of Haskell can be viewed as a simple extension of System F). In that case Spoon! is correct; in most flavors of System F, the fixpoint combinator must be a primitive. This follows from the fact that System F (without fix) is strongly normalizing. On the other hand it is not the case that "any recursion" requires the general recursive fixed-point combinator. Primitive recursion can be easily encoded using the Church numerals (which are definable in System F), and covers a variety of interesting recursive definitions. |
|||
On the other hand if we add recursive types, they provide a kind of loop-hole that allows us to type the standard fixed-point combinators from untyped lambda calculi; the linked message above demonstrates one way to do this. The addition of mutable state (a la lisp) also allows the definition of fixed point combinators IIRC. I believe (although I am less sure about this) that a call/cc primitive is also sufficent to define fixed point combinators. |
|||
At any rate, here is a way to define the Y combinator using recursive types in Haskell that is a little nicer than the one in the message above. |
|||
<lang haskell> |
|||
newtype Mu a = Roll { unroll :: Mu a -> a } |
|||
fix :: (a -> a) -> a |
|||
fix = \f -> (\x -> f (unroll x x)) $ Roll (\x -> f (unroll x x)) |
|||
fac :: Integer -> Integer |
|||
fac = fix $ \f n -> if (n <= 0) then 1 else n * f (n-1) |
|||
fibs :: [Integer] |
|||
fibs = fix $ \fbs -> 0 : 1 : fix zipP fbs (tail fbs) |
|||
where zipP f (x:xs) (y:ys) = x+y : f xs ys |
|||
main = do |
|||
print $ map fac [1 .. 20] |
|||
print $ take 20 fibs |
|||
</lang> |
|||
--RWD |