[tlug] Re: Y Combinator

[Edward Middleton <emiddleton@example.com>]

John Fremlin wrote:
> Edward Middleton wrote:
>> 1. http://www.eecs.harvard.edu/~cduan/technical/ruby/ycombinator.shtml
>
> If you looked at this code and actually understood what it was doing,
> I think it is basically this: (well at least it has the same results
> when I ran it)
>
> def make_hash_func()
>   Hash.new { |h, k| h[k] = make_hash_func }
> end

I guess you didn't read the part were he provided this solution and
commented on its shortcomings.

> The Y Combinator is for making an anonymous recursive function.
>
> I am sure that there are real uses for it. Can you provide an example
> in Haskell?

It is used in the implementation of the value recursion operator mfix[1]
for lists.

libraries/base/Control/Monad/Fix.hs

-- List:
instance MonadFix [] where
    mfix f = case fix (f . head) of
               []    -> []
               (x:_) -> x : mfix (tail . f)

> Seeing as it is part of the standard library one would hope that it
> was at least occasionally used.

I guess they decided they would splash out and add the two extra lines ;)

libraries/base/Data/Function.hs

fix :: (a -> a) -> a
fix f = let x = f x in x


Edward

1. http://leventerkok.googlepages.com/mfixTR.pdf or
http://leventerkok.googlepages.com/erkok-thesis.pdf