Fixed Point Generator in C# Generics

499 views Asked by At

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));
}
2

There are 2 answers

6
Lukazoid On BEST ANSWER

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);
}
1
ertes On

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