Wednesday, February 15, 2012

Variation on the State Monad in Scala


a brief one this evening, but I need to communicate. A friend of mine who recently read the post on the state Monad pattern asked me why I did not extend the generic Monad trait I was working on. 
Astute question. It took me some time to get an answer and provide him with a compiled version reproducing the canonical stack sample. I come today with a version, that, I submit to your judgement in need of feedbacks. As a reminder my previous proposal for both a Monad and a Functor trait lead me to:

No big deal. When I came to define the state Monad I bumped into a wall because of the expected behavior of the defintion of state Monad (from what I learnt for Learn You a Haskell). Roughly quoting the book, a stateful computation may be viewed as function taking as input some state and returning a value paired with some new state:

No matter how I took the problem I was facing two impediments
  • neither Function1[S, (A, S)] nor (S) => (A,S) are type constructors
  • Whatever would be the solution, I would have to work with a single argument type constructor  M[_]  while implementing Monad[M]
The first problem , I solved it mimicking Haskell creating a State class :

having at my hand a type constructor...alas with two type arguments. 

 The deal then was to freeze somehow one of the parameters in order to propose to the Monad trait to implement a single type parameter: from State[_, _] to M[_]
The method defintions in the generic Functor and Monad traits already fix the type parameter constraint as the type of the Monad returned value (in Haskell parlance). So obviously my Monad trait would have to be parameterized (<- neologism :)) with some kind of State[_, S] thing. 

Wait a minute. The idea would be to define my single argument type constructor under the scope of my state Monad definition, supposedly having "already" bound the State type (there is blur notion of "already" for me). It seems that the solution lays onto the use of a type lambda. As in the referenced article I have to "curry" somehow my double argument State[_,_] type constructor: 

The expression ({type λ[α] = State[α,S]}) seems to me like an anonymous structural type, the type I want being State[α,S]. The type S is "already" (still blur) bound to the State Monad implementation. We use then a type projection (aka #) in order to specify explicitly the λ type we expect as the single argument constructor. Roughly said, a type projection allows to refer to the  inner type in a type. All this is new for me and any pointer in addition to Joshua Suereth book will be welcome. 
All we need is a Kestrel combinator (look here and there for detailed explanation):

in order to use our State Monad in a for comprehension:

The complete code project can be found here.

The  implementation is naive and this field of Scala ramblings is new. Do not hesitate to feedback or to give pointers. 

Be seeing you !!! :)


Eric said...

Ah, the joys of type inference in Scala. Your post is a nice step-by-step explanation of how to do it.

Although the type lambda trick is a neat one and made things more accessible, the situation is still not ideal. This has been flagged a long time ago, for example here: (note the recent update by @milessabin which really help)

Marc-Daniel Ortega said...

Thank you for your feedback, I am going to check the pointer.

Post a Comment