Elm Codegen Quirks with Servant-Elm and Persistent

Developing further on the previous post, building some slightly less trivial examples with the combination of servant-elm and persistent (with Sqlite backend) yields some interesting problems in the generated Elm code. 

1. Phantom Types for Keys

Due to the way persistent handles database primary keys, servant-elm (via the underlying elm-bridge) currently generates Elm code with types such as Key World instead of WorldId, where, for Sqlite, ID variables are of type Int, used for database primary keys. 

But what is Key World in terms of Elm types? And what happens when you try to sequence a JSON encoder / decoder for Key (which doesn't exist!), along with a JSON encoder / ecoder for World -- something altogether different from the desired Int? 

type alias User  =
   { userEnv: (Key World)
   , userName: String

    [...]

jsonEncUser : User -> Value
jsonEncUser  val =
   Json.Encode.object
   [ ("userEnv", (jsonEncKey (jsonEncWorld)) val.userEnv)
   , ("userName", Json.Encode.string val.userName)
 

    [...]

There's some discussion of handling phantom types in elm-bridge, as well as some existing support for custom type replacements in the elm-bridge library.  To get it working, I ended up needing the custom type replacements, as well as some direct manipulation of the generated Elm code. (I also found some fairly extensive replacement ideas here).

The elm-bridge replacements are defined here: https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/make/Make/Spacemonkey.hs

That takes care of the instances of Key World and the like in Elm type definitions, but not in the API call functions, and also introduces a new problem of missing definitions for Id type encoders/decoders. 

type alias User  =

   { userEnv: WorldId

   , userName: String

   [...]

jsonEncUser : User -> Value

jsonEncUser  val =

   Json.Encode.object

   [ ("userEnv", jsonEncWorldId val.userEnv)

   , ("userName", Json.Encode.string val.userName)

   [...]

getWorldByWid : (Key World) -> (Result Http.Error  ((Maybe World))  -> msg) -> Cmd msg

getWorldByWid capture_wid toMsg =

    [...]

There may be some way to do replacements in a more integral way with the Template Haskell codegen, but I ended up just doing appends and naive text replacements on the final Elm output: https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/scripts/PostCodeGen.hs

2. Missing URL String Encoders

I also couldn't get servant-elm to generate correct URL string encoders, despite defining instances of toHttpApiData, which seems like it should be the thing to do. 

 

        Http.request
            [...]
            , url =
                Url.Builder.crossOrigin "http://localhost:8080"
                    [ "cellColor"
                    , (capture_worldid |> String.fromInt)
                    , (capture_x |> String.fromInt)
                    , (capture_y |> String.fromInt)
                    , (capture_color |> String.fromInt)
                    ]
             [...

... where Color is defined on the Haskell side as:

data Color
  = White
  | Yellow
  | Red
  | Green
  | Blue
  | Grey
  deriving (Show, Read, Eq, Generic, Enum, Bounded)

instance FromHttpApiData Color where
  parseUrlPiece :: T.Text -> Either T.Text Color
  parseUrlPiece = myParse

instance ToHttpApiData Color where
  toUrlPiece = T.pack . show
  toQueryParam = T.pack . show

So for each sum type instance, the post-code-gen script from above also takes care of the string encoders for use in URL building, appending the functions to the generated Elm code.

 

Wrapping Up

With the above edits, the Elm code gen + persistence layer stack works again. There was a lot more research and work(arounds) required this time, and I needed some help from friends at the Recurse Center, but it still (mostly!) satisfies the property of writing data definitions only once for the whole stack. It's not hard to see that some of the type mapping issues across languages and data boundaries are non-trivial to resolve, so I hope more usage and development goes into these kinds of type-safe stacks. 

Hello Server + Persistent

 The previous post covered setting up a Servant server in Haskell, with automatic codegen for Elm bindings and using the acid-state package for persistence. 

An obvious benefit of the stack is that one only ever needs to think in native Haskell data structures. It's relatively easy to use and achieves the goal of minimizing work across data boundaries (in this case, between the server and persistence layer). It's also self-contained, insofar as it doesn't require an external database server / process / engine.

On the other hand... many external database servers have been developed and refined for years -- if not decades -- yielding stability, tools, and all sorts of best practices and optimizations. 

Yesod's answer to the problem is persistent, which provides a type-safe and unified way to interact with a variety of database backends (primarily Sqlite, MySQL, Postgres, and MongoDB). Although the library was designed for Yesod, it is not tightly coupled and seems to work for Servant.

This file contains the data definitions for a revised version of Hello Server.  persist also uses Template Haskell, so we adapt the data declarations accordingly:

share
	[mkPersist sqlSettings , mkMigrate "migrateAll"]
	[persistLowerCase|
	ServerState
	state String
	counter Int
	deriving Eq Show Generic
	|]

Note that the servant-elm template invocations come later and works as expected -- i.e. first, persistent generates the ServerState data type and associate code it needs; then, servant-elm uses the generated ServerState data type for its purposes. 

This file contains the server instance, following the example in the Servant repo. 

And, with a few small changes on the Elm client side to accommodate API tweaks, it works!

There are a number of fundamental things I still haven't figured out (like... shouldn't the Sqlite connection pool be explicitly closed in the bracket pattern?). Overall, there are more things to think about compared to working with acid-state -- which seems reasonabl, since it corresponds to the relative power of the database engine (or at least, I assume so). Leveraging the "migrations" feature from persistent, though, I've still only written a single data definition in Haskell for the entire stack!

The repo with all examples: https://github.com/tkuriyama/spacemonkey

Hello Server + Acid-State

 The previous post covered defining a Servant server with automatic code generation for Elm bindings.

Are there libraries that allow for type-safe persistence in Haskell?

Again referring to the state of the Haskell ecosystem, one interesting library is acid-state, which provides ACID guarantees for de/serializing (serializable) Haskell data structures directly, with no external DBMS.

acid-state also uses Template Haskell, and it's relatively straightforward to augment the prior Hello Server data definitions. We define some simple operations we want (query, write), as well as the template invocations:

    $(deriveSafeCopy 0 'base ''ServerState)

    $(makeAcidic ''ServerState ['writeState, 'queryState])

On the server side,  this file has the updated logic to interact with the data store. Since acid-state uses monadic state, we can use ReaderT and again follow the Servant tutorial to thread the data state through the server calls. Although it doesn't seem strictly necessary given the acid-state guarantees, we can use the bracket pattern from Control.Exception to ensure that the data store is closed normally in the event of unexpected server failure.

That's pretty much it! As promised by the stack, generating the Elm code is just a matter of changing some filename configs in the code. In this case, the REST interface didn't change, so changing the backend had no impact on the rest of the client code. 

I haven't thought too much yet about the implications of this approach vs using some typed-SQL library like persistent, which I intend the try next.

Hello Server: Haskell + Elm Across Data Boundaries

 I started with the thought that it would be fun to write a small, private social network app in Elm, for family and friends to share. This immediately begs the question: what should the backend be? 

Setting aside for the moment the class of problems associated with running infrastructure with real users and data on the internet (e.g. security, availability, load, etc), there is the problem of type consistency and safety.

Maintaining safe, static data typing across data boundaries (say, client and server, or server and persistence layer) seems inherently tricky. Ideally, one wants to define data types (or data structures) somewhere,  exactly once, and have some abstractions and / or tools that propagate the type guarantees throughout the stack. That would safe effort, minimize boilerplate, and prevent typ(e)o-related errors!

The Elm ecosystem actually has Lamdera, whose the promise is that the server and persistence layers are abstracted away, leaving the developer to reason only about Elm data structures and what data maintain logically in the front vs back end. That's pretty much exactly what I want in this instance! Sadly, it remains in alpha, and doesn't appear to be open source for the moment.

Browsing through the State of the Haskell ecosystem, there are a variety of options for running servers and handling persistence in Haskell (the most obvious fit with Elm). Some of them look like they need project status updates (like Spock... people want to know the status, as it's been dormant for ~three years!). But of course I'm not the first to encounter this problem... so there are a few promising libraries. 

Haskell Server + Elm code gen + no persistence

The first is servant-elm, which wraps the elm-bridge library for use with the Servant webserver. 

Following Servant's tutorial and the servant-elm README on Github, we can:  

1. Define ADTs of our choice in Haskell, with corresponding typed REST APIs for Servant
2. auto-generate Elm code for corresponding data, including JSON serializers / deserializers that match the REST API (!)

This file defines the Haskell ADTs and API endpoints, with the Template Haskell line that servant-elm needs: deriveBoth defaultOptions ''ServerState

This file then defines the server logic, with an IORef to maintain some simple in-memory state.

Finally, this file actually generates the Elm module (well, the binary that generates the Elm module).

The resulting Elm code works as expected, albeit with some long function names!

To actually use the Elm client with localhost, I needed to start a temporary version of Chrome with some web security options disabled to account for CORS (borrowed from here).

Next post... adding persistence.

Parser Combinator for SQL Subset

Some more records from RC... a fellow Recurser and I presented on our toy SQL parser combinator at the Friday 5-minute talks (talk slides).

We actually ended up writing parser combinators from scratch twice during RC (first for CIS194 and again for fp-course). The two had almost identical primitives like satisfy :: (Char -> Bool) -> Parser Char, zeroOrMore, oneOrMore, and building up from there... which makes me wonder if there's just a standard recipe for parser combinators? 

For the toy SQL parser, we ended up referencing how Stephen Diehl uses Parsec in Kaleidescope once we defined the syntax. It turns our that Parsec provides a bunch of primitives we previously wrote ourselves, like brackets, parens, commaSep... But I think it would have taken us much longer to figure out how to use the package, were it not for Diehl's examples.

https://github.com/tkuriyama/toydb/blob/master/src/Database/Parser.hs

*Database.Parser> process "Insert Into myTable [1, True, \"Jonathan\"];"

Insert "myTable" [FvInt 1,FvBool True,FvText "Jonathan"]

*Database.Parser> process "Insert Into myTable [1, True, \"Jonathan\"]"

(line 1, column 42):

unexpected end of input

expecting ";"

*Database.Parser> process "Insert myTable [1, True];"

(line 1, column 8):

unexpected "m"

expecting "Into"

fp-course

Following the Learn Haskell recommendation, the FP study group at Recurse Center  worked through the fp-course exercises after finishing CIS 194. 

https://github.com/bitemyapp/learnhaskell

The exercises seem to provide good practice, with modules like State and StateT requiring some mental gymnastics training..! 

The repo unfortunately has some incomplete tests files, so I transcribed a few from the comments into HSpec format for Parser.hs and MoreParser.hs: https://github.com/tkuriyama/puzzles/tree/master/fp-course. 

The test cases were tedious but turned out to be worthwhile, since JsonParser.hs is comprised of more abstract parser combinators. (Interestingly, the parser combinator in CIS 194 is almost identical to fp-course in its building blocks... a coincidence, or a common design pattern?).

Anagrams and Cheque remain to be completed, but we're moving on to writing a toy database in Haskell (with the goal to complete in the last two weeks of the Fall 1 batch!).

Game of Risk Elm Visualization

Building on the previous post... an interactive(ish) Elm visualization of the game's probability trees: 

https://tarokuriyama.com/projects/risk.php

Game of Risk

The last assignment in the CIS194 Haskell class is to simulate dice-throwing battles in the game of Risk. The combat rules, taken from assignment specs, are:

• There is an attacking army (containing some number of units) and a defending army (containing some number of units). 
• The attacking player may attack with up to three units at a time. However, they must always leave at least one unit behind. That is, if they only have three total units in their army they may only attack with two, and so on. 
• The defending player may defend with up to two units (or only one if that is all they have). 
• To determine the outcome of a single battle, the attacking and defending players each roll one six-sided die for every unit they have attacking or defending. So the attacking player rolls one, two, or three dice, and the defending player rolls one or two dice. 
• The attacking player sorts their dice rolls in descending order. The defending player does the same.
• The dice are then matched up in pairs, starting with the highest roll of each player, then the second-highest.
• For each pair, if the attacking player’s roll is higher, then one of the defending player’s units die. If there is a tie, or the defending player’s roll is higher, then one of the attacking player’s units die.

We assume it is optimal to always attack or defend with as many units as possible.

Given an initial number of attacking and defending units, what is the expected outcome (say, the probability that the attacker wins)? 

It's not obvious that there is a closed-form expression, but we can find programmatically the exact probabilities. 

First, from the game specs, we know that there are only a few primitive battle patterns (A, D), where A is attacked and D is defender: (1, 1), (2, 1), (3, 1), (1, 2), (2, 2), (3, 2). For each pattern, we can generate all possible permutations of die values. Each permutation represent a battle, with an outcome ("loss scenario") in which A and D both lose some number of units (which can be zero units, if they win all dice rolls).  

For example, for (A,D) of (1,1), both the attacker and defender role one die each, yielding 36 pairs of possible die rolls: (1,1), (1,2), (1,3) ... (6,5), (6,6). Tallying up the proportion of outcomes: A loses 1 unit 21 / 36; D loses 1 unit 15 / 36.

(Incidentally, the closed-form expression for 1 vs 1 is relatively simple: for each N that the defender rolls, with 1/6 probability each, the attacker loses in N/6 scenarios. For example, if the defender rolls 4, the attacker loses for all die values <= 4. So we can evaluate the expression (1/6) * (sum [1..6]) / 6, which equals 21/36. See these notes for a more detailed explanation.)

Once we have the loss scenarios with proportions for each primitive battle pattern, finding the exact win probability for the attacker is recursive: for any given starting pattern (A, D), lookup the relevant primitive battle pattern. For each loss scenario in which the attacker does not lose the game, update the battlefield with the losses and recursively lookup the next loss scenario, chaining the proportions (probabilities) until the game ends for each branch. 

The win probabilities for the attacker for patterns up to (10, 10) are:

The Haskell implementation for the above is in this gist. 

Using Rational numbers in Haskell allows the answers to be expressed exactly. For example for (4,2), the win probability for A is 6610505 % 10077696 (see the rightmost column here). 

Mini Regex

Hacker News linked to Brian Kenighan's post about a small regex matcher, which seemed like a good bite-sized problem to try implementing -- both in general and for practicing Haskell, particularly with this being a pattern matching problem.

Following Kernighan's specifications, the regex language is limited to:

    c    matches any literal character c
    .    matches any single character
    ^    matches the beginning of the input string
    $    matches the end of the input string
    *    matches zero or more occurrences of the previous character

To make the exercise a bit more stateful, I chose to implement find (return the left-most occurrence of a pattern that matches the regex, if it exists), instead of just indicating the presence of a match. There is minimum lookahead required -- just one character to detect boundaries for the Kleene star.

I first tried to implement find with a lazy map over the tails of the input (returning the head as the left-most match), but ran into the problem of inputs with no matches. Since I couldn't find an out-of-box function, mapUntil implements a map that stops when a non-default value is found, and otherwise returns the default value. This also has the benefit of using an empty string to indicate no match, which is more direct here than, say, using Maybe. Always wrapping and unwrapping the input with the start and end sentinels seemed like a reasonable price to avoid introducing special cases later on.

find :: Regex -> String -> Match
find r s = unwrap $ mapUntil "" (findWord r) (tails $ wrap s)
  where wrap xs = ('^':xs) ++ "$"
        unwrap xs = [c | c <- xs, c `notElem` ['^', '$']]

mapUntil :: Match -> (String -> Match -> Match) -> [String] -> Match
mapUntil d _ [] = d
mapUntil d f (x:xs) = if m /= d then m else mapUntil d f xs
  where m = f x ""

The core matching function covers four patterns: non-star regex, star regex, the regex is consumed (success), or otherwise failure.

findWord :: Regex -> String -> Match -> Match
findWord (x:'*':xs) s@(y:ys) ms = findWord xs ys' (reverse ms'++ ms)
  where (ms', ys') = if not (match x y) then ("", s) else splitWhile (matchStar x xs) s
findWord (x:xs) (y:ys) ms = if match x y then findWord xs ys (y:ms) else ""
findWord "" _ ms = reverse ms
findWord _ _ ms = ""

Match is very simple. MatchStar needs a bit of extra state, since '.*' matching should stop if the next part of the regex matches input.

match :: Char -> Char -> Bool
match x y = x == '.' || x == y

matchStar :: Char -> String -> Char -> Bool
matchStar x [] y = match x y
matchStar x (x':xs) y = (x == '.' && x' /= y) || x == y

SplitWhile seems like it should exist... it calls both takeWhile and dropWhile, so could be rewritten more efficiently to require only single pass over the input.

splitWhile :: (a -> Bool) -> [a] -> ([a], [a])
splitWhile f xs = (takeWhile f xs, dropWhile f xs)

There are a few reverses and concatenations, which weren't immediately obvious to me to refactor into more efficient patterns. Code with some hand-written test cases: https://gist.github.com/tkuriyama/f60210a0e6dfa5bc0872494afaa0030b

F# and Functional Pearls

After encountering the language last year, I've finally gotten around to studying F# from Expert F#. So far, the language has proven much friendlier than Haskell (though it's not really a fair comparison since I'm now more aware of functional constructs).

As practice, I've started implementing some Project Euler problems in F#. I've also been working on porting some Haskell "functional pearls" from Richard Bird's excellent book Pearls of Functional Algorithm Design. The going is slow but rewarding, as it's turning out to be a great way to practice F# while also learning more about functional programming in general.

One chapter that I've worked on is the "countdown" problem, in which the goal is to use some numbers from a given list to generate an arithmetic expression that evaluates to a value as close to target as possible. For example, given a list of numbers [1, 3, 7, 10, 25, 50] and a target of 831, the solution is: 

> display(countdown1 831 [1;3;7;10;25;50]);;

(7+((1+10)*(25+50))) = 832

https://github.com/tkuriyama/functional-pearls/tree/master/countdown

The "Unfaithful" Sieve of Eratosthenes

I recently came across this bit of Python code on Stack Overflow, in a post that asked for an elucidation of the lambda predicates involved:

primes = range(2, 20) 
for i in range(2, 8): 
     primes = filter(lambda x: x == i or x % i, primes)

This is basically functional-esque code for something that resembles a naive implementation of the Sieve of Erastothenes. Given an input list of integers to start, the algorithm iterates through a second list of integers and uses the lambda predicates to filter the input list such that only primes remain. (The upper bound of 8 for the second list appears arbitrary; it's also a suboptimal upper bound given the input upper bound of 19, but we can ignore that here.)

As far as a naive implementation goes, it's arguably more elegant in a pure functional form like the following (in Haskell):

sieve          :: [Integer] -> [Integer]
sieve []        = []
sieve (p:xs)    = p : sieve [x | x <- xs, x `mod` p > 0]

The Haskell version can be called like so:

sieve [2..19]

As it turns out, though, this is a sieve by trial division rather than the true Sieve of Eratosthenes. Although the underlying logic is similar, the implementation of the algorithm is sufficiently different that the "unfaithful" sieve suffers from noticeably worse time complexity. A quick Google search immediately brings up literature on the subject: The Genuine Sieve of Eratosthenes.

Think like a Fundamentalist, Code like a Hacker...

I've just finished Eric Meijer's Intro to Functional Programming on edX. Since the course was taught in Haskell, I also managed to get my feet wet with the language and now feel prepared to work through Learn You a Haskell and Real World Haskell.

One of the course's mantras has been "think like a fundamentalist, code like a hacker". The idea is to start with an approach that is fundamentally correct and iteratively refine the implementation. This is a pretty convincing philosophy for Haskell (and perhaps functional programming in general), since things like type checking and pattern matching facilitate reasoning about the correctness of programs. An interesting question that follows, however, is how to balance readability/clarity vs the efficiency of solutions that are fundamentally sound but "hacked".

There's a good example in Graham Hutton's Programming in Haskell called "Making Append Vanish" (chapter 13, section 6). We start with an example of a recursive function that reverses the elements of a list:

reverse              :: [a] -> [a]
reverse []            = []
reverse (x:xs)        = reverse xs ++ [x]

Because this solution using the ++ append operator is relatively inefficient (requiring quadratic time), Hutton demonstrates using induction that a linear time solution can be derived:

reverse              :: [a] -> [a]
reverse xs            = reverse' xs []


reverse'             :: [a] -> [a] -> [a]
reverse' [] ys        = ys
reverse' (x:xs) ys    = reverse' xs (x:ys)

At least for me, the second solution takes much longer to digest, and hence is less clear -- but it is demonstrably correct and far more efficient. I'm not sure if it's really fair to call the second solution "hacked". But it does illustrate an interesting aspect of the functional programming paradigm, which I'm looking forward to exploring further.

The Haskell Affair

http://www.xent.com/pipermail/fork/Week-of-Mon-20070219/044101.html

Hiatus and Haskell

I've been on hiatus as I started a new job this year... but I have resumed some coursework and hope to document progress on a more regular basis.

Erik Meijer's Introduction to Functional Programming on EdX has been an excellent (and gentle) introduction to the subject, and has also served as a good way to dive into Haskell. I suspect Learn You a Haskell will be much easier to digest after this course.