How do I combine Result and State in Elm?

Question

I am struggling with Elm's lack of monads. A library implementing the state monad for Elm (http://package.elm-lang.org/packages/folkertdev/elm-state/latest/State) has helped me quite a bit.

The problem is that I have now run into a situation where I have alternately nested Result and State types, when I only want to have one of each.

I tried to write a function with the following signature, but it seems impossible, because the inner Result is only known once the outer State is evaluated.

join : Result a (State s (Result a (State s x))) -> Result a (State s x)

Maybe it would work if I put the Result inside the State in the return value, but that would generate a dummy State in case the outer Result is Err.

I think the right idea would be to make something that is both Result and State. Can someone who is familiar with Haskell monad transformers explain how they solve this kind of problem or suggest an alternative solution?

Here is a rough version of one place where the problem arises:

  generateConstraints environment value
  |> Result.map (State.map (\(value, valueC) ->
    Result.map
      (State.map2 (\this (body, bodyC) ->
        ( this
        , valueC ++ bodyC ++ [(this, body)]
        ))
      freshTypevar)
      (generateConstraints (extend environment name value) body))
  )

Answer 1

Can someone who is familiar with Haskell monad transformers explain how they solve this kind of problem or suggest an alternative solution?

Well, I can at least try. This is how your type looks directly translated to Haskell:

type EffM a s x = Either a (State s x)

A rather obvious observation is that it's not a monad transformer.² That's how a transformer would look like:

type TransM a s x = EitherT a (State s) x

As you can see, the only change is the T and the fact that x is outside the parens. The latter part is essential in understanding the transformer approach.

The core idea is that the State is a part of the result production regardless of whether the Either results in "success" or "fail", whereas in your case producing "fail" means the state operation is never touched. I'd need to think harder what that means in practice, but intuitively the transformer approach is what you're gonna have in mind when working with typical, imperative code.

Now, when you use such a transformer, join is actually provided for free, as a consequence of fitting into the Monad interface.

import Control.Monad.State
import Control.Monad.Trans.Either
import Control.Monad

type Eff e s a = EitherT e (State s) a

-- type the following in REPL

λ :t join
join :: Monad m => m (m a) -> m a

λ :t join :: Eff e s (Eff e s a) -> Eff e s a
join :: Eff e s (Eff e s a) -> Eff e s a
     :: Eff e s (Eff e s a) -> Eff e s a

-- the slightly cryptic output above means that it typechecks correctly

So this is how Haskell¹ solves it. Now, it's obviously possible to write a specialized EitherState type this way (altough I'd personally flip those two in all of the examples to StateEither - feels more natural), mirroring what the implementation of join for respective transformers would do. I don't know if writing EitherT specifically is possible in Elm.

---

¹ One possible approach. There are other, recursion schemes/Free probably being the one to watch in the upcoming years. The inherent ordering of effects stacking turns out to be more problematic than it initially seems.

² It's also not a Monad, at least in the sense that the x can't be the direct type in the Monad instance (because Either can obviously act as one in the specialized case).

Answer 2

I ended up writing a monad that is both. I had to sacrifice the ability to fail before State is touched, because I need to be able to fail after.

type alias Infer a = State Int (Result String a)

infer : a -> Infer a
infer x =
  State.state (Ok x)

map : (a -> value) -> Infer a -> Infer value
map f x =
  State.map (Result.map f) x

andThen : (a -> Infer b) -> Infer a -> Infer b
andThen f x =
  State.andThen
    (\r -> case r of
      Ok v -> f v
      Err e -> State.state <| Err e
    )
    x

andMap : Infer y -> Infer (y -> z) -> Infer z
andMap y =
  andThen (\g -> map g y)

map2 : (a -> b -> c) -> Infer a -> Infer b -> Infer c
map2 f x y =
  map f x
  |> andMap y

map3 : (a -> b -> c -> d) -> Infer a -> Infer b -> Infer c -> Infer d
map3 f a b c =
  map2 f a b
  |> andMap c

map4 : (a -> b -> c -> d -> e) -> Infer a -> Infer b -> Infer c -> Infer d -> Infer e
map4 f a b c d =
  map3 f a b c
  |> andMap d