Functionele concepten in OO

[Amras]

Met de komst van function delegates is het mogelijk om bepaalde concepten uit functionele programmeertalen als Haskell toe te passen in C#. Populaire blogonderwerpen zijn function memoization, currying en partial function application en monads.

Nu vind ik dit allemaal enorm interessant en ik heb daarom al flink wat van deze blogposts gelezen. Ook heb ik mijn Haskell-kennis afgestoft en aan de hand van een gratis boek wat oefeningen gedaan om weer wat feeling te krijgen met functioneel programmeren. Het begint allemaal enigzins te dagen (al vind ik het concept monad nog erg wazig), maar ik vraag mij toch wel af wat het nut van deze concepten is in mijn alledaagse programmeerwerk.

Er komen natuurlijk voorbeelden voorbij in blogs, maar de meeste zijn niet erg nuttig. Zo geloof ik inderdaad wel dat je door middel van currying een optelfunctie zoals hieronder kunt uitvoeren, maar dit heeft volgens mij weinig voordelen ten opzichte van een add functie met twee parameters.

C#:

public static Func<A, Func<B, R>> Curry<A, B, R>(this Func<A, B, R> f)
{
  return a => b => f(a, b);
}

Func<int,int,int> add = (x,y) => x + y;
Func<int,Func<int,int>> curriedAdd = add.Curry();

int i = curriedAdd(3)(5)

Function memoization lijkt mij persoonlijk handig in het geval van recursie, zoals het fibonacci-voorbeeld in deze post. Zo zijn er waarschijnlijk meer toepassingen waarin het vasthouden van het resultaat van een functie voor een bepaalde set parameters een performancewinst kan opleveren, al zou je dit natuurlijk ook buiten de functie kunnen cachen.

Over monads durf ik nog niet veel te zeggen, aangezien ik die zelf nog niet goed doorgrond en het nut dan lastig te bepalen is. Wel begreep ik dat IEnumerable<T> in .NET een voorbeeld is van een monad en dat ik er dus nu al voordeel van heb. Graag zou ik wat meer te weten komen over het herkennen van monads en situaties waarin ik een monad zou kunnen toepassen.

Mijn vraag aan jullie: gebruiken jullie deze concepten nu in je allerdaagse programmeerwerk? En zo ja: heb je een goed voorbeeld waarin dit een significant voordeel biedt ten opzichte van een 'klassieke' C# oplossing?

Graag word ik overtuigd zodat ik deze sjeike functies aan een standaard set van extensions methods kan toevoegen.

[Caelorum]

Misschien is dit wel interresant om wat ideeën/inspiratie van op te doen: http://channel9.msdn.com/...11-Netherlands/Devdays097

[RayNbow]

Amras schreef op donderdag 23 juni 2011 @ 15:11:
Wel begreep ik dat IEnumerable<T> in .NET een voorbeeld is van een monad en dat ik er dus nu al voordeel van heb. Graag zou ik wat meer te weten komen over het herkennen van monads en situaties waarin ik een monad zou kunnen toepassen.

Het herkennen van een monad is net zoiets als het herkennen dat een lijst en een set beide enumereerbaar zijn. Je hebt er niet direct baat bij, maar wanneer je merkt dat iets enumereerbaar is, kun je meteen alle bestaande IEnumerable-gerelateerde functies en patronen toepassen.

Bij monads is het net zo. Als je merkt dat Foo<T> een monad is (Eigenlijk hoor ik te zeggen dat dan Foo de monad is, niet Foo<T>.), dan kun je alle bestaande monad functies gebruiken. Nu is het alleen zo dat het schrijven van generieke monad functies lastig is in C# (typesystem is niet krachtig genoeg), maar je kunt wel voor elke monad de LINQ syntax gebruiken.

Er komen natuurlijk voorbeelden voorbij in blogs, maar de meeste zijn niet erg nuttig. Zo geloof ik inderdaad wel dat je door middel van currying een optelfunctie zoals hieronder kunt uitvoeren, maar dit heeft volgens mij weinig voordelen ten opzichte van een add functie met twee parameters.

Currying heeft in C# helaas weinig voordelen, omdat de syntax van de taal er zich niet voor leent. Maar in een taal als Haskell waar alles standaard gecurryd en de syntax voor functieapplicatie licht is (namelijk een spatie), zijn er bepaalde zaken een stuk aangenamer op te schrijven.

* RayNbow heeft nu alleen geen tijd om daar verder op in te gaan... misschien later op de dag

[Avalaxy]

Waarom C#? Maak een .NET solution aan in Visual Studio met daarin een C# project, bouw alles wat je maar wilt in C# en schrijf de dingen die je functioneel wilt in F# (in een aparte F# project). 2 Talen binnen 1 solution is geen enkel probleem en werkt perfect samen. Het mooie is dat F# echt voor functioneel programmeren bedoeld is (officieel is het multi-paradigma, maar OOP of imperatief programmeren in F# is nogal lame als dat ook gewoon in C# kan).

Edit: ik had alleen je titel gelezen niet het topic. Bovenstaande info is dus nutteloos voor jou (wellicht wel nuttig voor een andere gebruiker die zoekt op dit onderwerp).

Recursie gebruiken voor stomme dingetjes als Fibonacci reeksen berekenen zou ik persoonlijk overigens afraden in een OOP taal, zorgt alleen maar voor slechtere performance en de mogelijkheid tot stack overflow exceptions.

[Voor 30% gewijzigd door Avalaxy op 23-06-2011 23:05]

[Amras]

Caelorum schreef op donderdag 23 juni 2011 @ 15:31:
Misschien is dit wel interresant om wat ideeën/inspiratie van op te doen: http://channel9.msdn.com/...11-Netherlands/Devdays097

Zeker interessant! Heb de eerste 45 minuten gekeken en daar kwamen wel wat leuke dingen voorbij. Ik lees de blog van Bart de Smet af en toe, maar dat gaat soms wel heel erg diep. Slimme vent, dat wel.

RayNbow schreef op donderdag 23 juni 2011 @ 15:58:
[...]


Het herkennen van een monad is net zoiets als het herkennen dat een lijst en een set beide enumereerbaar zijn. Je hebt er niet direct baat bij, maar wanneer je merkt dat iets enumereerbaar is, kun je meteen alle bestaande IEnumerable-gerelateerde functies en patronen toepassen.

Bij monads is het net zo. Als je merkt dat Foo<T> een monad is (Eigenlijk hoor ik te zeggen dat dan Foo de monad is, niet Foo<T>.), dan kun je alle bestaande monad functies gebruiken. Nu is het alleen zo dat het schrijven van generieke monad functies lastig is in C# (typesystem is niet krachtig genoeg), maar je kunt wel voor elke monad de LINQ syntax gebruiken.

Het voorbeeld van de Maybe monad voor null propagation in bovenstaand filmpje heeft wel het één en ander verhelderd. Mooie toepassing van het concept, wat zeker bruikbaar is.

Currying heeft in C# helaas weinig voordelen, omdat de syntax van de taal er zich niet voor leent. Maar in een taal als Haskell waar alles standaard gecurryd en de syntax voor functieapplicatie licht is (namelijk een spatie), zijn er bepaalde zaken een stuk aangenamer op te schrijven.

* RayNbow heeft nu alleen geen tijd om daar verder op in te gaan... misschien later op de dag

Dat dacht ik inderdaad al. Dat maakt het schrijven van de Curry extension method van hierboven een leuke oefening, maar de toegevoegde waarde is dus nihil. Mocht je nog tijd en zin hebben om dieper op de voordelen van currying in Haskell in te gaan, dan houd ik mij aanbevolen.

Avalaxy schreef op donderdag 23 juni 2011 @ 23:02:
Waarom C#? Maak een .NET solution aan in Visual Studio met daarin een C# project, bouw alles wat je maar wilt in C# en schrijf de dingen die je functioneel wilt in F# (in een aparte F# project). 2 Talen binnen 1 solution is geen enkel probleem en werkt perfect samen. Het mooie is dat F# echt voor functioneel programmeren bedoeld is (officieel is het multi-paradigma, maar OOP of imperatief programmeren in F# is nogal lame als dat ook gewoon in C# kan).

Edit: ik had alleen je titel gelezen niet het topic. Bovenstaande info is dus nutteloos voor jou (wellicht wel nuttig voor een andere gebruiker die zoekt op dit onderwerp).

Hier was ik inderdaad van op de hoogte, maar toch bedankt. Het is zeker een goede optie om bepaalde functionaliteit in een F# project te stoppen, als je de volledige voordelen van functioneel programmeren wilt gebruiken.

Recursie gebruiken voor stomme dingetjes als Fibonacci reeksen berekenen zou ik persoonlijk overigens afraden in een OOP taal, zorgt alleen maar voor slechtere performance en de mogelijkheid tot stack overflow exceptions.

Daar loop je helaas al vrij snel tegenaan ja. Jammer, want het levert wel de meest elegante oplossing op. Gelukkig kom ik de Fibonacci reeks weinig tegen tijdens het schrijven business applicaties, maar er zijn zeker wel voorbeelden te bedenken waarin recursie goed toepasbaar zou zijn. Function memoization kan dan een mooie techniek zijn om de performance wat te verbeteren.

[RayNbow]

Amras schreef op vrijdag 24 juni 2011 @ 08:05:
[...]

Het voorbeeld van de Maybe monad voor null propagation in bovenstaand filmpje heeft wel het één en ander verhelderd. Mooie toepassing van het concept, wat zeker bruikbaar is.

Jawel, maar de Maybe monad is slechts 1 enkel voorbeeld van een monad, net zoals dat bijv. een LinkedList slechts 1 enkel voorbeeld van een IEnumerable is. Er bestaan zo veel verschillende monads.

Ik raad trouwens aan om Commutative Monads, Diagrams and Knots te kijken voor wat meer leuke voorbeelden van monads.

Addendum: Hier is trouwens een (versimpelde) vergelijking tussen Haskell's do-syntax en de LINQ syntax:

code:

-- Haskell                  |// C#
----------------------------|//--------------------------------------------
r = do x <- f a b           |      var r = from x in f(a,b)
       y <- g c d           |              from y in g(c,d)
       return (x + y)       |              select x + y;
                            |
                            |
                            |
r = do x <- f a             |      var r = from x in f(a)
       g b                  |              from _ in g(b)
                            |              select _;
                            |
                            |
                            |
-- 'return' is captured in  |      // Depends on monad:
-- the Monad type class     |      static IEnumerable<T> Unit<T>(T t) {
-- and is polymorphic       |          return Enumerable.Repeat(t, 1); }
                            |      
r = do x <- return a        |      var r = from x in Unit(a)
       y <- return b        |              from y in Unit(b)
       return (x + y)       |              select x + y;
                            |

[...]

Dat dacht ik inderdaad al. Dat maakt het schrijven van de Curry extension method van hierboven een leuke oefening, maar de toegevoegde waarde is dus nihil. Mocht je nog tijd en zin hebben om dieper op de voordelen van currying in Haskell in te gaan, dan houd ik mij aanbevolen.

Ik zal proberen om wat tijd te vinden om hierop in te gaan.

[Voor 37% gewijzigd door RayNbow op 24-06-2011 08:55]

[RayNbow]

RayNbow schreef op vrijdag 24 juni 2011 @ 08:27:
[...]

Ik zal proberen om wat tijd te vinden om hierop in te gaan.

Okay, ik zal proberen om alvast een paar voordelen van currying (i.c.m. met een licht verteerbare syntax) op te noemen.

De eerste is partial application die je al in je topic start noemde. Nu is dit niet zo'n groot voordeel, aangezien je dit ook met lambda's kunt bereiken. Als je een 2-ary functie in C# hebt waarvan je alleen het eerste argument alvast van wilt invullen, dan schrijf je simpelweg (y => f(3, y)).

Een ander voordeel is eta-reductie. De volgende definities van de twee sum-functies zijn identiek:

Haskell:

sum1 xs = foldr (+) 0 xs
sum2 = foldr (+) 0

Met currying geldt ook dat diff en deriv gelijk zijn:

Haskell:

diff f = f'
  where
    f' x  =  (f (x+h) - f x) / h
    h     =  0.0001

deriv f x = (f (x+h) - f x) / h
  where h = 0.0001

Wat ik zelf echter tot nu toe het fijnste vind aan currying is dat het erg helpt op type-niveau. Functors (en ook monads aangezien monads functors zijn) zijn type constructors F die 1 type parameter vragen en verder nog voldoen aan bepaalde eigenschappen (waarvan ik straks er 1 behandel). Een voorbeeld van een functor in .NET is List:

• List<int>, bijv., is een type;
• List is de type constructor.

Een van de eigenschappen van een functor F is dat je de volgende functie kunt schrijven:

Haskell:

fmap :: (a -> b) -> F a -> F b

Of in C# syntax:

C#:

F<B> FMap(Func<A,B> f, F<A> x) {
    // ...
}

De bovenstaande functie is trouwens een van de LINQ operators en heeft de naam Select.


Een ander voorbeeld van een type constructor in .NET is Dictionary. Dictionary vraagt echter 2 type parameters, namelijk een voor de keys en een voor de values: Dictionary<K,V>. Als je de K vast zou kunnen zetten (net zoals bij partial function application), dan krijg je een type constructor die nog maar 1 type parameter zou vragen. Deze type constructor is een functor aangezien je gemakkelijk de volgende functie zou kunnen definieren:

C#:

// pseudo-C# met ondersteuning van gecurryde type constructors
(Dictionary<K>)<B> FMap(Func<A,B> f, (Dictionary<K>)<A> x) {
    // ...
}

De kracht van gecurryde type constructors zit hem vooral in de mogelijkheid om beter te kunnen abstraheren. Met C# generics kun je al restricties opleggen, zoals in het onderstaande voorbeeld:

C#:

void Foo<T>(IEnumerable<T> t) where T : IComparable<T> {/*...*/}

Maar als we ook over type constructors kunnen praten, dan zouden we dingen als hieronder kunnen schrijven:

C#:

// pseudo-C# met higher kinds
void Bar<T>(F<int> t) where F : Functor {/*...*/}

[Amras]

Allereerst bedankt voor je uitgebreide post!

Die eta-reductie is ook mogelijk in C#, maar levert door de benodigde haakjes voor functiecalls inderdaad weinig op:

C#:

public static int Sum1(int[] xs)
{
    return xs.Aggregate((a, b) => a + b);
}

public static Func<int[], int> Sum2()
{
    return xs => xs.Aggregate((a, b) => a + b);
}

int sum1 = Sum1(items);
int sum2 = Sum2()(items);

De voordelen van functors voor C# vind ik nog wat lastig te doorgronden. In je laatste voorbeeld zou F bijvoorbeeld een IEnumerable kunnen zijn, maar ook een totaal ander type (niet gerelateerd aan collecties van objecten) wat een int als eerste type parameter heeft. Of sla ik de plank nu volledig mis? In dat geval heb ik nog wat moeite met het bedenken van situaties waarin ik deze constructie zou gebruiken, maar dat zou ook een gebrek aan creativiteit van mijn kant kunnen zijn.

[RayNbow]

[b]Amras schreef op maandag 27 juni 2011 @ 13:35:
De voordelen van functors voor C# vind ik nog wat lastig te doorgronden. In je laatste voorbeeld zou F bijvoorbeeld een IEnumerable kunnen zijn,

Yup, IEnumerable is een functor.

maar ook een totaal ander type constructor (niet gerelateerd aan collecties van objecten)

Het kan inderdaad een andere type constructor zijn...

wat een int als eerste type parameter heeft.

...maar die type constructor heeft niet per se een int "als eerste" type parameter. Neem voor F bijvoorbeeld Dictionary<string>. Dan is F<int> dus Dictionary<string, int>. Hierbij is int niet de eerste type parameter, maar de tweede.

Een ander voorbeeld van een functor is Func<A> van Func<A,B>. Hier begint de notatie trouwens problematisch te worden vanwege overloading. .NET heeft types als Func<A>, Func<A,B>, Func<A,B,C>, et cetera. Met de eerdere geintroduceerde pseudo-syntax kan het nu onduidelijk zijn wat ik met Func<A> bedoel. Bedoel ik het type Func<A> of bedoel ik de type constructor Func<A> waarmee ik het type Func<A,B> kan construeren? In dit geval bedoel ik in ieder geval het laatste.

Als uitdaging, probeer F<B> FMap(Func<A,B> f, F<A> x){ /* .. */ } te schrijven voor F=Func<A>.

In dat geval heb ik nog wat moeite met het bedenken van situaties waarin ik deze constructie zou gebruiken, maar dat zou ook een gebrek aan creativiteit van mijn kant kunnen zijn.

Situaties bedenken is altijd lastig. Zeker wanneer de gegeven voorbeelden beetje kunstmatig zijn.

[RSchellhorn]

Hoi Amras,

tijd niet gesproken!

Het mixen van het functionele en OO paradigma is iets wat je nu eigenlijk in alle talen ziet optreden, niet alleen C#, maar ook op het Java platform (Scala) en natuurlijk in Ruby. Hoe goed OO ook is in het beschrijven van data, manipuleren kan een draak zijn. Neem bijvoorbeeld het filteren van collecties (omdat ik uit de Java hoek, een voorbeeldje in Java):

Java:

List<Person> people = someListWithPeople;
List<Person> peopleLivingInUtrecht = new ArrayList<Person>();
for (Person person : people) {
    if (person.location == Utrecht) {
        peopleLivingInUtrecht.add(person);
    }
}

Een functionele aanpak is veel leesbaarder, door gebruik te maken van een functie predicaat:

Scala:

val people = someListWithPeople
val peopleLivingInUtrecht = people.filter ( person => person.location == Utrecht )

Dit is slechts een voorbeeld, er zijn er veel meer te verzinnen (pattern matching for the world!). Al met al denk ik dat deze concepten steeds slimmer samengevoegd worden. Dit is typisch een gevalletje 1+1=3, de combinatie voegt net dat beetje extra toe.

Ik zeer blij dat ik meer en meer Scala mag gebruiken, in plaats van Java. Dus om antwoord te geven op je vraag: ja, ik gebruik naast OO ook de functionele eigenschappen van mijn taal.

[Amras]

Gelukkig is er in C# op dit gebied al een hoop mogelijk na de introductie van Linq, lambda expressions en extensions methods in C# 3.0. Jouw voorbeeld is dan ook eenvoudig als volgt te schrijven in C#:

C#:

var peopleLivingInUtrecht = people.Where(p => p.Location == "Utrecht");

Deze constructies zijn niet meer weg te denken in applicaties die tegenwoordig in .NET worden geschreven, omdat het compactere code oplevert die ook nog eens beter leesbaar is. Java loopt wat dat betreft wat achter de feiten aan, voor zover ik weet.

Waar ik in dit topic naar toe wilde is een discussie over het gebruik van meer geavanceerdere functionele concepten als currying en monads. Je ziet momenteel veel blogposts voorbij komen waarin de meest geniale en abstracte functies voorbij komen, waarvan ik mij afvraag of je dit ook daadwerkelijk in productiecode wilt gebruiken of dat het slechts een leuke oefening is. Tot nu toe voel ik mij nog niet genoodzaakt om extensions methods voor currying (zoals in de startpost) en function memoization toe te voegen aan een standaard library.

Natuurlijk zijn dit soort experimenten met een taal de opstap naar nieuwe bruikbare features. Door functionele constructies te integreren in de taal C# en het .NET platform kunnen we nu gebruik maken van LINQ en krijgen we in de toekomst beschikking over Reactive Extensions. Het begrip van concepten als monads helpt je dan om dit soort frameworks beter te begrijpen.

RSchellhorn schreef op zondag 10 juli 2011 @ 13:25:
tijd niet gesproken!

offtopic:
Inderdaad! How's life? DM anders even, dat scheelt wat vervuiling in dit topic. (had je al geprobeerd een DM te sturen, maar die heb je uit staan)

RayNbow schreef op maandag 27 juni 2011 @ 14:45:
Als uitdaging, probeer F<B> FMap(Func<A,B> f, F<A> x){ /* .. */ } te schrijven voor F=Func<A>.

Deze uitdaging ben ik op mijn werk aangegaan en heb de functie geïmplementeerd voor Func<A>, Dictionary<K,V> en List<T>. Helaas heb ik hier thuis de source code niet beschikbaar, maar die kan ik morgen eventueel nog wel posten.

Situaties bedenken is altijd lastig. Zeker wanneer de gegeven voorbeelden beetje kunstmatig zijn.

Het blijft inderdaad allemaal erg kunstmatig en daarom zie ik nog geen directe reden om dit nu actief in mijn C# code te gaan gebruiken. Toch blijven het leuke oefeningen en het helpt volgens mij wel bij het beter begrijpen van frameworks als LINQ, zoals ik hierboven al noemde.

[voodooless]

Amras schreef op zondag 10 juli 2011 @ 14:30:
Java loopt wat dat betreft wat achter de feiten aan, voor zover ik weet.

Dat mag dan wel zo zijn, maar met Java 78 zijnworden een heleboel van deze concepten wel geïntroduceerd, zie ook hier.

[Voor 3% gewijzigd door voodooless op 26-07-2011 17:27]

[creator1988]

voodooless schreef op dinsdag 26 juli 2011 @ 17:24:
[...]


Dat mag dan wel zo zijn, maar met Java 78 zijnworden een heleboel van deze concepten wel geïntroduceerd, zie ook hier.

Ik hoor al sinds 2006 dat dit er bijna in zit. Vooralsnog moet ik nog maar zien of Java 8 binnen 5 jaar uitkomt.

[voodooless]

Klopt. In de tussentijd is er nog wel lamdaj, al vind ik de performance niet echt impressive..