2

I have tried to define a fixed point generator in C# that you see in many functional languages. I believe foldr is usually defined in terms of a fixed point generator sometimes. I'll show it's Haskell definition and then what I have in C#. Any help is greatly appreciated.

//Haskell
fix f = f (fix f)

//C# (Many attempts)
public static Func<Func<T, T>, T> Combinator1<T>(this Func<T, T> f)
{
    return x => f(Combinator1(f)(x));
}
public static Func<Func<T, T>, T> Combinator2<T>(this Func<T, T> f)
{
    return x => x(Combinator2(x)(f));
}
public static Func<T, U> Combinator3<T, U>(Func<Func<T, U>, Func<T, U>> f)
{
    return f(x => Combinator3(f)(x));
}
duplode
  • 33,731
  • 7
  • 79
  • 150
Aaron Stainback
  • 3,489
  • 2
  • 31
  • 32

2 Answers2

4

I don't have much understanding of haskell or this operator. But I have read an article from Mads Torgersen about implementing the Y/Fix combinator using C# lambda expressions. It may be of some use to you, here is the link.

And here is the final method he implements:

public Func<T, T> Fix<T>(Func<Func<T,T>, Func<T,T>> F) {
  return t => F(Fix(F))(t);
}
Lukazoid
  • 19,016
  • 3
  • 62
  • 85
  • 3
    See also our former colleague Wes Dyer's post on the same subject: http://blogs.msdn.com/b/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx – Eric Lippert Jan 10 '12 at 23:19
  • @EricLippert Thanks for the link, I'm taking the time at last to make sense of it all – Lukazoid Jan 10 '12 at 23:30
  • Thanks it looks like on all three cases I was a somewhat wrong :) What really messed me up was I tried to copy paste the Haskell syntax into F# to see the types but F# missed the implicit x. it should have been 'let rec fix f x = f (fix f) x' in F# Thanks so much for your help. – Aaron Stainback Jan 10 '12 at 23:41
  • On another note, I thought Fix and Y were two different combinators. Are they in fact the same? Thanks. – Aaron Stainback Jan 10 '12 at 23:43
  • 2
    @AaronStainback: Y is an *example* of a fixed-point combinator, and is an exceptionally *simple* fixed-point combinator, so it is often spoken of as "the" fixed-point combinator when speaking casually. There are in fact infinitely many fixed-point combinators, so speaking of "the" fixed-point combinator is misleading. – Eric Lippert Jan 11 '12 at 00:14
  • 1
    @EricLippert Thank you for this information it clears a lot of things up. I've tried to clean up the question. – Aaron Stainback Jan 11 '12 at 02:25
4

First of all, the Y combinator is a particular implementation in untyped lambda calculus. We are talking more generally about fixed point combinators.

All the answers given here show excellently why fixed point combinators don't really make sense without currying. The one given by Lukazoid is not as general as it should be. It has this type (in Haskell notation):

lukazoidFix :: ((a -> b) -> a -> b) -> a -> b

A real fixed point combinator should be much more polymorphic.

fix :: (a -> a) -> a
ertes
  • 2,287
  • 15
  • 10
  • I think that only works in a normal-order language. In an applicative-order language like C# (or even the ML family), Lukazoid's answer is correct. – kvb Jan 11 '12 at 15:34