Sunday, October 21, 2012 – 122 views
— by joefiorini
Haskell’s function composition blows my mind. Let's implement a Caesar Cipher.
A Caesar Cipher is a very, very primitive form of encrypting messages. Take a message, such as:
We're bombing the storage depots at Daiquiri at 1800 hours. We're coming in from the north, below their radar.
What's the simplest thing we could do to encrypt this message? What if we shifted each letter up by one? Then we'd have:
XF'SF CPNCJOH UIF TUPSBHF EFQPUT BU EBJRVJSJ BU 1800 IPVST. XF'SF DPNJOH JO GSPN UIF OPSUI, CFMPX UIFJS SBEBS.
To make it a little more cryptic you could shift the letters by more characters:
OW'JW TGETAFY LZW KLGJSYW VWHGLK SL VSAIMAJA SL 1800 ZGMJK. OW'JW UGEAFY AF XJGE LZW FGJLZ, TWDGO LZWAJ JSVSJ.
What would it take to implement this as a function in Haskell? Well, first off we'd want to give it a string and an offset like so:
caesar 18 "We're bombing the storage depots at Daiquiri at 1800 hours. We're coming in from the north, below their radar."
A basic implementation would be:
caesar offset msg = map (\c -> (chr ((ord c) + offset))) msg
map function takes two parameters: an anonymous function that is the map operation and the list to iterate over. So we're mapping over our string message, which performs the map operation on each character in the string.
chr ((ord c) + offset)
For each character we get the ASCII integer representing that character, add offset to it and then convert that integer back to a corresponding ASCII character with the
chr function (these are all built into Haskell's standard library).
This is pretty succinct and readable once you understand it. However, every time you call a function in Haskell it actually returns itself as another function that won't be called until necessary. Therefore we could write this as:
caesar offset = map (\c -> (chr ((ord c) + offset)))
Haskell also supports function composition. Oh noes. Math. Function composition (f(g(x) = f • g) just means you can pass one function to another and it's parameters will automatically come along with it. Using this feature we could write our Caesar cipher as:
caesar offset = map (chr . (+ offset) . ord)
The parameter that's passed into the map operation is automatically passed into each function that needs it. Cool, eh?
0 Replies – 0 Reposts – 0 Stars