Haskell: Trying to make tapyclasses ala Rust dyn Trait for a FSM

Question

I am a Haskell beginner, And I am trying to make a Finite State machine in Haskell like the one that Rob Pike show in his conference about Lexing and Go. Trough Rust-like dyn Traits.

Like this one.

pub struct Something {
    something: bool,
}

pub trait Saladable {
    fn next(&self, state: Something) -> (Box, Something);
}

struct A;
struct B;

impl Saladable for A {
    fn next(&self, state: Something) -> (Box, Something) {
        match state.something {
            true => (Box::new(A {}), Something { something: false }),
            false => (Box::new(B {}), Something { something: false }),
        }
    }
}

impl Saladable for B {
    fn next(&self, _state: Something) -> (Box, Something) {
        (Box::new(A {}), Something { something: true })
    }
}

But when trying to convert it to Haskell

{-# LANGUAGE AllowAmbiguousTypes #-}
module Main where

main = undefined

data Something = Something Bool

class Saladable m where
  next :: Saladable f => Something -> (Something, f)

data A = A
data B = B

instance Saladable A where
  next (Something True) = (Something False, A)
  next (Something False) = (Something False, B)

instance Saladable B where
  next _ = (Something True, A)

I get this error

Test.hs:15:45: error:
    • Couldn't match expected type ‘f’ with actual type ‘A’
      ‘f’ is a rigid type variable bound by
        the type signature for:
          next :: forall f. Saladable f => Something -> (Something, f)
        at Test.hs:15:3-6
    • In the expression: A
      In the expression: (Something False, A)
      In an equation for ‘next’:
          next (Something True) = (Something False, A)
    • Relevant bindings include
        next :: Something -> (Something, f) (bound at Test.hs:15:3)
   |
15 |   next (Something True) = (Something False, A)
   |                                             ^

Test.hs:19:29: error:
    • Couldn't match expected type ‘f’ with actual type ‘A’
      ‘f’ is a rigid type variable bound by
        the type signature for:
          next :: forall f. Saladable f => Something -> (Something, f)
        at Test.hs:19:3-6
    • In the expression: A
      In the expression: (Something True, A)
      In an equation for ‘next’: next _ = (Something True, A)
    • Relevant bindings include
        next :: Something -> (Something, f) (bound at Test.hs:19:3)
   |
19 |   next _ = (Something True, A)
   |

Why I like is a idea of why this is happening, and how I can done to replicate that behavior of Rust.

user_15207568 · Answer

I think this is the most direct translation of that Rust code:

{-# LANGUAGE ExistentialQuantification #-}

data Something = Something Bool

data SomeSaladable = forall a. Saladable a => SomeSaladable a

class Saladable a where
  next :: (a, Something) -> (SomeSaladable, Something)

data A = A
data B = B

instance Saladable A where
  next (_, Something True) = (SomeSaladable A, Something False)
  next (_, Something False) = (SomeSaladable B, Something False)

instance Saladable B where
  next _ = (SomeSaladable A, Something True)

Here the SomeSaladable contains an existentially quantified type, see this wikibook page for more info.

But really, this is an antipattern in Haskell. Note that this next function can now no longer be chained. You have to unwrap the resulting SomeSaladable, so this is a pain to use.

A common solution can be found by asking: if you know that the only thing you can do with the resulting Saladable is to run the next function, then why don't you just store that? If you do that then you get something like this:

data Something = Something Bool

data Saladable = Saladable (Something -> (Saladable, Something))

next :: (Saladable, Something) -> (Saladable, Something)
next (Saladable f, x) = f x

a, b :: Saladable
a = Saladable (\(Something x) ->
  case x of
    False -> (a, Something False)
    True -> (b, Something False))

b = Saladable (\_ -> (a, Something True))

Haskell: Trying to make tapyclasses ala Rust dyn Trait for a FSM

1 Answers