• Choose a category
• All
• Classic-Fiction

ord 'a' returns 97 because 'a' is the ninety-seventh character in the Unicode table of characters.

The difference between the ord values of two characters is equal to how far apart they are in the Unicode table.

Let’s write a function that takes a number of positions to shift and a string, and returns that string where every character is shifted forward in the alphabet by that many positions.

import Data.Char

encode :: Int -> String -> String

encode offset msg = map (\c -> chr $ ord c + offset) msg

Encoding a string is as simple as taking our message and mapping over it a function that takes a character, converts it to its corresponding number, adds an offset, and then converts it back to a character. A composition cowboy would write this function as (chr . (+ offset) . ord).

ghci> encode 3 "hey mark"

"kh|#pdun"

ghci> encode 5 "please instruct your men"

"uqjfxj%nsxywzhy%~tzw%rjs"

ghci> encode 1 "to party hard"

"up!qbsuz!ibse"

That’s definitely encoded!

Decoding a message is basically just shifting it back by the number of places it was shifted by in the first place.

decode :: Int -> String -> String

decode shift msg = encode (negate shift) msg

Now we can test it by decoding Caesar’s message:

ghci> decode 3 "kh|#pdun"

"hey mark"

ghci> decode 5 "uqjfxj%nsxywzhy%~tzw%rjs"

"please instruct your men"

ghci> decode 1 "up!qbsuz!ibse"

"to party hard"

On Strict Left Folds

In the previous chapter, you saw how foldl works and how you can use it to implement all sorts of cool functions. However, there’s a catch to foldl that we haven’t yet explored: Using foldl can sometimes lead to so-called stack overflow errors, which occur when your program uses too much space in a specific part of your computer’s memory. To demonstrate, let’s use foldl with the + function to sum a list that consists of a hundred 1s:

ghci> foldl (+) 0 (replicate 100 1)

100

This seems to work. What if we want to use foldl to sum a list that has, as Dr. Evil would put it, one million 1s?

ghci> foldl (+) 0 (replicate 1000000 1)

*** Exception: stack overflow

Ooh, that is truly evil! Now why does this happen? Haskell is lazy, and so it defers actual computation of values for as long as possible. When we use foldl, Haskell doesn’t compute (that is, evaluate) the actual accumulator on every step. Instead, it defers its evaluation. In the next step, it again doesn’t evaluate the accumulator, but defers the evaluation. It also keeps the old deferred computation in memory, because the new one often refers to its result. So as the fold merrily goes along its way, it builds up a bunch of deferred computations, each taking a not insignificant amount of memory. Eventually, this can cause a stack overflow error.

Here’s how Haskell evaluates the expression foldl (+) 0 [1,2,3]:

foldl (+) 0 [1,2,3] =

foldl (+) (0 + 1) [2,3] =

foldl (+) ((0 + 1) + 2) [3] =

foldl (+) (((0 + 1) + 2) + 3) [] =

((0 + 1) + 2) + 3 =

(1 + 2) + 3 =

3 + 3 =

6

As you can see, it first builds up a big stack of deferred computations. Then, once it reaches the empty list, it goes about actually evaluating those deferred computations. This isn’t a problem for small lists, but for large lists that contain upward of a million elements, you get a stack overflow, because evaluating all these deferred computations is done recursively. Wouldn’t it be nice if there was a function named, say, foldl', that didn’t defer computations? It would work like this:

foldl' (+) 0 [1,2,3] =

foldl' (+) 1 [2,3] =

foldl' (+) 3 [3] =

foldl' (+) 6 [] =

6

Computations wouldn’t be deferred between steps of foldl, but would get evaluated immediately. Well, we’re in luck, because Data.List offers this stricter version of foldl, and it is indeed called foldl'. Let’s try to compute the sum of a million 1s with foldl':

ghci> foldl' (+) 0 (replicate 1000000 1)

1000000

Great success! So, if you get stack overflow errors when using foldl, try switching to foldl'. There’s also a stricter version of foldl1, named foldl1'.

Let's Find Some Cool Numbers

You’re walking along the street,