In my previous post, I showed an example of where the lack of higher-kinded types in .NET (both C# and F#) induces the need for code repetition. In this post I’ll show you how higher-kinded type support in Haskell allows for the elimination of this repetition.
LINQ
First, let’s take our LINQ query and translate it into Haskell syntax. As a reminder, here’s the query.
|
1 2 3 4 5 6 7 8 9 |
static IEnumerable<string> GetPurchaseLogs( IEnumerable<Person> people, IEnumerable<Purchase> purchases) { return from person in people from purchase in purchases where person.Id == purchase.PurchaserId select person.Name + " purchased " + purchase.ItemName; } |
Haskell Translation
In Haskell syntax, that translates directly to:
|
1 2 3 4 5 6 |
getNotices :: [Person] -> [Purchase] -> [String] getNotices people purchases = do person <- people purchase <- purchases guard $ (pid person) == (personId purchase) return $ (name person) ++ " purchased a " ++ (itemName purchase) |
Remember “IEnumerable<T>” in C# is (for our purposes) equivalent to “[T]” in Haskell. Also “where” is equivalent to “guard”, and “return” is like “select”.
Haskell Use
Let’s use it in a full program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
import Control.Monad -- our two datatypes from the LINQ/Rx example data Person = Person {pid :: Int, name :: String} deriving (Show) data Purchase = Purchase {personId :: Int, itemName :: String} deriving (Show) -- our select function getNotices :: [Person] -> [Purchase] -> [String] getNotices people purchases = do person <- people purchase <- purchases guard $ (pid person) == (personId purchase) return $ (name person) ++ " purchased a " ++ (itemName purchase) -- some examples main = do -- define people let alice = Person 1 "Alice" bob = Person 2 "Bob" -- define purchase records apple = Purchase 1 "apple" altimeter = Purchase 1 "altimeter" bayonet = Purchase 2 "bayonet" -- show notices on list print $ getNotices [alice, bob] [apple, bayonet, altimeter] |
The results:
|
1 2 3 |
[ "Alice purchased a apple", "Alice purchased a altimeter", "Bob purchased a bayonet" ] |
Great! So now we can do LINQ-like queries in Haskell.
Higher-kinding things
But, remember in the previous post I said that LINQ is equivalent to a MonadPlus abstraction, which is a monad with filtering (where-clause) capability. And if you look above, you’ll see that getNotices also only uses the MonadPlus interface of the List class. So let’s abstract the type signature of this function.
|
1 2 3 4 5 6 |
getNotices :: MonadPlus m => m Person -> m Purchase -> m String getNotices people purchases = do person <- people purchase <- purchases guard $ (pid person) == (personId purchase) return $ (name person) ++ " purchased a " ++ (itemName purchase) |
Note we didn’t have to change the implementation at all. All we had to do was to update the type signature to say “don’t limit me to a List, but rather allow anything that is a MonadPlus”. We compile that, and great, no errors!
An Example
Now, Haskell does not have Rx, but let’s test this against one of the more common monads, the Maybe monad:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
main = do -- define people let alice = Person 1 "Alice" bob = Person 2 "Bob" -- define purchase records apple = Purchase 1 "apple" altimeter = Purchase 1 "altimeter" bayonet = Purchase 2 "bayonet" -- show various notices on maybe print $ getNotices (Just alice) (Just apple) print $ getNotices Nothing (Just apple) print $ getNotices (Just bob) (Just apple) print $ getNotices (Just alice) Nothing print $ getNotices Nothing Nothing |
The results:
|
1 2 3 4 5 |
Just "Alice purchased a apple" Nothing Nothing Nothing Nothing |
Awesome, so the same logic can be reused on List types *and* Maybe types, which cannot be done on .NET!
Going Crazy!
Now for a more complicated example, when looking at the documentation I noticed that STM (Software Transactional Memory) is also of type MonadPlus. What would that mean? Looking through the documentation of STM, you can find that when the guard fails, the transaction retries until it succeeds. So it’s essentially a transaction that keeps on retrying not only until the execution was atomic, but also until the input data is what it wants. Great, how can we test this? Here’s a function I created to test it.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
main = do -- define people let alice = Person 1 "Alice" bob = Person 2 "Bob" -- define purchase records apple = Purchase 1 "apple" altimeter = Purchase 1 "altimeter" bayonet = Purchase 2 "bayonet" -- show notice on STM personVar <- newTVarIO bob purchaseVar <- newTVarIO apple forkIO $ do threadDelay 1000000 atomically $ writeTVar personVar alice notice <- atomically $ getNotices (readTVar personVar) (readTVar purchaseVar) print notice |
What happens here? The STM vars are initialized with incompatible person/purchase. So the guard fails, the transaction is retried (for the performance-concerned: it does not sit in a spin loop retrying the transaction, but smartly sleeps until either of the vars is updated) until the vars are compatible, and atomically blocks at the second-last line. So then in another thread, the STM var is updated to compatible alice, the transaction completes, the notice is returned, and the main thread prints it out.
Summary
Can I think of a real-world use case for using STM this way? Well, probably not for logs, but maybe in a banking scenario where the transaction has to not only be atomic, but also ensure the account balance stays positive. That could be a topic for another post. But for now it’s just interesting to see how higher-kinded types allow one piece of logic to be used in so many completely different ways. I hope you enjoyed this exercise as much as I did.