Translating Haskell Expression Problem Solution to Scala 3

Question
1

Hi all,

Having worked on The Expression Problem - Part 1 (download for proper image quality), I am now starting out on Part 2, and I am asking myself if it is possible to translate the following Haskell solution of the Expression Problem into Scala 3.

module Main where

import Lib

data Const = Const Int
data Add l r = Add l r

class Expr x
instance Expr Const
instance (Expr l, Expr r) => Expr (Add l r)

class Expr x => Evaluate x
  where evaluate :: x -> Int

instance Evaluate Const
  where evaluate (Const i) = i

instance (Evaluate l, Evaluate r) => Evaluate (Add l r)
  where evaluate (Add l r) = evaluate l + evaluate r

------------------------------------------------------------
-- Add a new expression type without modifying existing code

data Neg x = Neg x

instance Expr x => Expr (Neg x)

instance Evaluate x => Evaluate (Neg x)
  where evaluate (Neg x) = 0 - evaluate x

------------------------------------------------------------
-- Add a new function without modifying existing code

class Expr x => Stringify x
  where toString :: x -> String

instance Stringify Const
  where toString (Const i) = show i

instance (Stringify l, Stringify r) => Stringify (Add l r)
  where toString (Add l r) = "(" ++ (toString l) ++ "+" ++ (toString r) ++ ")"

instance Stringify x => Stringify (Neg x)
  where toString (Neg x) = "-" ++ (toString x)

-------------------------------------------------------
-- Try it out

four = Const 4
twoPlusThree = Add (Const 2) (Const 3)
twoPlusThreeNegated = Neg (Add (Const 2) (Const 3))

main :: IO ()
main = do
  
  putStrLn (show (evaluate four))
  putStrLn (show (evaluate twoPlusThree))
  putStrLn (show (evaluate twoPlusThreeNegated))
  
  putStrLn (show (toString four))
  putStrLn (show (toString twoPlusThree))
  putStrLn (show (toString twoPlusThreeNegated))

A quick way of running this code is to simply paste it in https://replit.com/languages/haskell and click ‘Run’.

Here is the output:

$ main
4
5
-5
"4"
"(2+3)"
"-(2+3)"

As soon as I begin, I get stuck:

case class Const(c: Int)
case class Add[A](l: A, r: A)

trait Expr[A] { }

given Expr[Const] with { }
given expr[A](using l: Expr[A], r: Expr[A]): Expr[Add[Expr[A]]] with { }

Simple scala typeclasses were sufficient to translate the code seen in the above deck, but I reckon I need to learn a great deal in order to attempt this.

Can anyone help?

What Scala 3 features are necessary to pull this off?

I would be grateful for any form of help: pointers to relevant language features/papers/videos, suggestions, examples, code snippets.

Thank you in advance for your help,

Philip

1 Like
2

Here’s one way to do it:

2 Likes
3

Here’s my solution using type classes only:

case class Const(c: Int)
case class Add[A, B](l: A, r: B)
case class Neg[A](a: A)

trait Expr[A]
given Expr[Const] with { }
given AddExpr[A, B](using leftExpr: Expr[A], rightExpr: Expr[B]): Expr[Add[A, B]] with { }
given NegExpr[A](using expr: Expr[A]): Expr[Neg[A]] with { }

trait Eval[A] {
    def eval(a: A)(using expr: Expr[A]): Int
}
given ConstEval: Eval[Const] with {
    def eval(a: Const)(using expr: Expr[Const]) = a.c
}
given AddEval[A, B](using leftExpr: Expr[A], rightExpr: Expr[B], leftEval: Eval[A], rightEval: Eval[B]): Eval[Add[A, B]] with {
    def eval(a: Add[A, B])(using expr: Expr[Add[A, B]]) = leftEval.eval(a.l) + rightEval.eval(a.r)
}
given NegEval[A](using expr: Expr[A], subEval: Eval[A]): Eval[Neg[A]] with {
    def eval(a: Neg[A])(using expr: Expr[Neg[A]]) = -subEval.eval(a.a)
}

val four = Const(4)
val twoPlusThree = Add(Const(2), Const(3))
val twoPlusThreeNegated = Neg(twoPlusThree)

def eval[A](a: A)(using expr: Expr[A], eval: Eval[A]) = eval.eval(a)
println(eval(four))
println(eval(twoPlusThree))
println(eval(twoPlusThreeNegated))

(I left out Stringify because it can be done like Eval.)

That’s a hard read but the code can be simplified by merging Expr and Eval:

case class Const(c: Int)
case class Add[A, B](l: A, r: B)
case class Neg[A](a: A)
  
trait Expr[A] {
    def eval(a: A): Int
}
given Expr[Const] with {
    override def eval(a: Const) = a.c
}
given AddExpr[A, B](using leftExpr: Expr[A], rightExpr: Expr[B]): Expr[Add[A, B]] with {
    override def eval(a: Add[A, B]) = leftExpr.eval(a.l) + rightExpr.eval(a.r)
}
given NegExpr[A](using expr: Expr[A]): Expr[Neg[A]] with {
    override def eval(a: Neg[A]) = -expr.eval(a.a)
}
  
val four = Const(4)
val twoPlusThree = Add(Const(2), Const(3))
val twoPlusThreeNegated = Neg(twoPlusThree)
  
def eval[A](a: A)(using expr: Expr[A]) = expr.eval(a)
println(eval(four))
println(eval(twoPlusThree))
println(eval(twoPlusThreeNegated))

If the modularity provided by type classes is not important, then subclassing with type boundaries will do the job:

trait Expr {
    def eval: Int
}

case class Const(c: Int) extends Expr {
    def eval = c
}
case class Add[A <: Expr, B <: Expr](l: A, r: B) extends Expr {
    override def eval = l.eval + r.eval
}
case class Neg[A <: Expr](a: A) extends Expr {
    override def eval = -a.eval
}

val four = Const(4)
val twoPlusThree = Add(Const(2), Const(3))
val twoPlusThreeNegated = Neg(twoPlusThree)
println(four.eval)
println(twoPlusThree.eval)
println(twoPlusThreeNegated.eval)

In all three approaches, serialization (Stringify) can be implemented by implementing toString for the case classes.

2 Likes
4

@alex.boisvert @informarte awesome - thank you very much - just printed your solutions out - it is nice an sunny here, so I will have a good look at them while out on a walk

5

Thank you @alex.boisvert - nice proposal - I hadn’t even considered using subtype polymorphism for Expr, because I was focused on the fact that in the first deck it was associated with OO being closed to the addition of new functions, but because you are already achieving additivity for functions by other means, subtype polymorphism is fine here as it allows you to make the expression data type open to new subtypes.

6

Thank you @informarte - great effort! - I had a quick stab at comparing your first solution with the original and if I am not wrong there is a huge amount of symmetry.

image
image1920×1077 222 KB

As I said earlier, I got stuck when I found myself writing code like this:

trait Expr[A] { }

given Expr[Const] with { }
given expr[A](using l: Expr[A], r: Expr[A]): Expr[Add[Expr[A]]] with { }

I hadn’t come across givens whose behaviour is nonexistent, and they didn’t seem to make much sense to me, but your perseverance seems to show that such givens (or rather, your version of them) can be used to impose useful constraints.

I am assuming that your Add uses two types (A and B), because you found it impossible to use just one, but I’ll double check when I get a chance.

1 Like
7

I’d think that’s just due to faithful translation - it’s two different types in the original Haskell code, as well.

1 Like
8

You are right, thanks for pointing that out. I have been seeing too many expression evaluation Scala programs using a single type for the expressions to be added or multiplied :slightly_smiling_face:.

9

@informarte - FYI, your solution features in The Expression Problem - Part 2 - thanks again.

1 Like