Understanding a simple string algorithm in Haskell

Here’s an implementation of the “mocking spongebob” meme in Haskell:

import Data.Char

spongemock = zipWith ($) (cycle [toUpper, toLower])

And we can use it, of course:

> spongemock "hello there, world!"
"HeLlO ThErE, wOrLd!"

> spongemock "i'm in your area"
"I'M In yOuR ArEa"

This transforms a string character by character, alternating between uppercasing and lowercasing each one.

I think it’s pretty cool how we can implement this operation in a single line of code, so let’s break it down!

I’ll assume that you possess a very vague idea of what Haskell is, but have some intuition in popular, traditional languages such as Python or JavaScript. If you already understand the Haskell code above, you’ll probably find this post boring. Go do something cool instead!

Functions#

Before we get into the code, we need to understand how functions work in Haskell, as they behave a bit differently than in other languages.

Let me start off by saying that Haskell blurs the line between functions and values. In Haskell, functions are values, and can be passed around as such within your code. In fact, you can treat functions as “partial values”, or “values that are awaiting other values before they may be evaluated”. This is an extremely powerful tool.

The syntax we use to define top-level values is incredibly close to the syntax we use to define top-level functions, as you’ll see in a bit.

Currying#

In Haskell, all functions are “curried”. This means that all functions accept one parameter. In order to simulate multiple parameters, we can have the function evaluate to another function that takes yet another parameter.

Here’s what this would look like in JavaScript:

function add(x) {
	return function (y) {
		return x + y;
	};
}

To use this, we do add(5)(10), as opposed to something like add(5, 10). Interestingly, we can do something like add(5) and store it for later, maybe in a variable called addFive:

const addFive = add(5);

const ten = addFive(5);

We’ll revisit this idea later on.

In Haskell, all functions are like this. Define a function that appears to take two parameters and you’ll get a function like the above instead automatically.

To demonstrate this, let’s take a look at the function signature of the + “operator”, which is actually just a function that can be applied with infix notation (meaning it can be smushed between two values, just we do in math class).

Let’s ask GHCi, the Glasgow Haskell Compiler’s interactive environment, for the type of the + operator–err, I mean function. This is possible through the :type incantation.

Here we go. GHCi?

> :type (+)

(+) :: Num a => a -> a -> a

For our purposes, let’s pretend the Num typeclass doesn’t exist and instead substitute the constraint for concrete types:

(+) :: Int -> Int -> Int

Ah, that’s better.

Haskell uses the Num typeclass to express the idea of “something shaped like a number”. This is good as it allows (+) to be used on all sorts of number-shaped thingies, instead of being forced to commit to an actual number type. After all, there is more than one number type in Haskell. For our purposes, though, let’s just pretend that (+) only works on Integers. Pretending is fun, right?

In a language without curried functions, you might’ve expected something like (Int, Int) => Int instead. After all, addition involves two numbers and evaluates to one number.

We can read (+) :: Int -> Int -> Int as “function (+) takes an integer, evaluates to another function that takes an integer, then finally evaluates to an integer.” This is just like that JavaScript example above.

The arrow, (->), associates to the right, so we can read it as:

(+) :: Int -> (Int -> Int)

By the way, + is surrounded by parentheses so that we may refer to it as a function. When a function’s name is nothing but symbols, we need to do that in order to refer to it in normal contexts.

Let’s use (+):

(+) 5 10 -- 5 + 10

In Haskell, functions are evaluated by specifying the name of said function, and supplying an argument separated by a space. Of course, if we’d like, we can use infix notation:

5 + 10

But let’s use (+) here. What’s going on in (+) 5 10? It looks like we’re supplying two arguments. In reality though, we’re only applying one at a time.

(Side note: You might be used to “calling” functions. In Haskell, we say “applying” functions instead.)

(+) 5 10 is actually ((+) 5) 10. Function application in Haskell is the operation with the highest precedence, and it’s left associative. We evaluate (+) 5, then apply 10 to that. No tricks here–functions still only accept one parameter at a time.

Translating Haskell’s ((+) 5) 10 to JavaScript, we get add(5)(10), just like above.

Each time we apply, we’re shedding one layer of nested functions, until there’s no more and we have the value we wanted.

This happens every time we have a function that accepts “multiple parameters”. As it turns out, though, only giving some parameters can have its uses!

Partial application#

Applying a function with only some inputs is called “partial application”. (+) 5 (or add(5) in JavaScript according to our previous definitions) is deemed partial application.

We’ve already given the addition operator 5, and we still need another number. This is represented as the type of (+) 5 itself, Int -> Int. This means that (+) 5 is a function! Then we apply 10 to that function and get 15.

-- No application yet.
(+)      -- :: Int -> Int -> Int

-- Apply once.
(+) 5    -- :: Int -> Int

-- Apply twice!
(+) 5 10 -- :: Int

15       -- :: Int

Partial application is cool, and it lets us be expressive. Let’s define our own functions with partial application.

addFive = (+) 5
-- addFive 20 = 25

double = (*) 2
-- double 5 = 10

Here’s a JavaScript equivalent:

// Functions in JavaScript are not curried, so we must do it manually.
function add(x) {
	return function (y) {
		return x + y;
	};
}

const addFive = add(5);
// addFive(20) = 25

// Ditto...
function multiply(x) {
	return function (y) {
		return x * y;
	};
}

const double = multiply(2);
// double(5) = 10

“Sectioning” lets us write it another way if our heart desires it so:

-- Previously... (+) 5
addFive = (+ 5)

-- Previously... (*) 2
double = (* 2)

Okay, back to the spongemock thing.

import Data.Char

spongemock = zipWith ($) (cycle [toUpper, toLower])

It turns out that we are partially evaluating zipWith here. That is, we’re not providing an argument to it. This “required argument” is actually the input string that we end up providing to the function:

> spongemock "i am trapped in this machine"
"I Am tRaPpEd iN ThIs mAcHiNe"

Here is equivalent code where no partial evaluation takes place:

import Data.Char

spongemock input = zipWith ($) (cycle [toUpper, toLower]) input

In Haskell, we define top-level functions and values (again, functions are values) with the equal sign. We can specify parameters to our function definitions just as we apply them within function bodies–a space, and a name. Here, we accept input and pass it to zipWith as the “third” argument.

However, due to partial evaluation, we can completely leave it off, and it’ll be completely equivalent. Going back to the (+) examples:

-- These two functions are the same.

addFive number = number + 5

addFiveCooler  = (+ 5)

Despite addFiveCooler not having a parameter in its definition, it still accepts one due to the partial evaluation of (+).

If we think of functions as “values that are waiting on other values”, then we’ve made the value we’re waiting for explicit in our definition of addFive.

In addFive, we chant to GHC: “we demand a number!” But there’s no need to do that in addFiveCooler, as we are partially evaluating (+).

(+ 5) is a function, and assigning that value to addFiveCooler means it behaves exactly as if it were a function that accepted a parameter, like our boring addFive friend.

To sum it all up, because Haskell functions can only take one parameter at a time, we have to “nest” functions if we want to have them accept more than one. This has the side effect of being able to only provide some arguments. Any leftover required arguments are just functions within functions. And because functions are values, they are very malleable, and there are multiple ways to deal with ‘em.

Point-free#

Refusing to explicitly mention the actual arguments of a function is called “point-free style”, and is generally considered desirable.

f x = x + 1

g = (+ 1)

h = \x -> x + 1

f, g, and h all behave equivalently. g is point-free. h uses “anonymous function” syntax that we haven’t seen before. This is equivalent to x => x + 1 in JavaScript or lambda x: x + 1 in Python.

Zipping#

Okay. Phew. Now what the hell is zipWith? Let’s have a look at zip first, which is closely related:

> zip [1, 2, 3] [4, 5, 6]
[(1,4),(2,5),(3,6)]

It takes two lists and turns it into one by grabbing from each list in parallel and pairing them up into tuples from left to right. Hmm…

> :type zip
zip :: [a] -> [b] -> [(a, b)]

In Haskell, generic types are typically represented with lowercase letters such as a and b. This type signature that GHCi just gave is a formalization of what I just described zip’s behavior to be.

Because a and b, are, well, different letters, we can zip lists of different types:

> zip [1, 2, 3] ["one", "two", "three"]
[(1,"one"),(2,"two"),(3,"three")]

Cool. Now what does zipWith do?

> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

It needs a function that accepts an a and b and evaluates to some value of type c. Then you apply a list of type a and a list of type b, and out comes a list of type c.

This is zip, but instead of stuffing a and b into a tuple, we are able to pass a function in order to do whatever we want with those values, even transforming it into another type if we’d like (c). Then that all gets shoved into a list from left to right just like before.

An example:

> zipWith (+) [10, 20, 30] [1, 2, 3]
[11,22,33]

-- The same as [10 + 1, 20 + 2, 30 + 3].

Here, we pretend (+) is Int -> Int -> Int again. Then we can additionally pretend that we are passing [Int], then [Int]. Finally, out comes [Int].

The types check out:

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

-- (+) is our (a -> b -> c). This fixes a, b, and c to all be Int.
-- [a] is therefore [Int], and we pass that ([10, 20, 30]).
-- [b] is therefore [Int] as well, and we pass that ([1, 2, 3]).
-- [c] is an [Int] too, and it's [11, 22, 33].

How does this help us here?

import Data.Char

spongemock = zipWith ($) (cycle [toUpper, toLower])

We are zipping whatever cycle [toUpper, toLower] is with the input list, and using the ($) function to combine them. Let’s investigate that first list there, which is being passed into the cycle function. But first, we need to learn about…

Laziness!#

Haskell is lazy. This means that nothing is evaluated unless it needs to be.

This has both advantages and disadvantages. I’ll just be touching on the fun parts, though.

Laziness enables us to construct so-called “infinite lists”:

> take 5 [1..]
[1,2,3,4,5]

Here, [1..] is an infinite list of incrementing integers that begin from 1 and proceed forever. (Again, uh… they’re technically not integers. But we’re pretending that all of our numbers are integers for the sake of simplicity.)

The take function does exactly what it says on the tin–take n elements from a list. Because Haskell didn’t bother to evaluate the infinite list, it only evaluated the first five values, the ones we wanted!

What happens if we try to evaluate the entire list, though? Let’s try summing, instead; an operation that requires traversal of the entire data structure:

> sum [1..]
-- Oh...

^C^C^C^C

Yeah, it freezes. Laziness enables us to be expressive, but can lead to problems if we aren’t cautious. Let’s try more interesting operations on infinite lists:

> take 10 (filter even [1..])
[2,4,6,8,10,12,14,16,18,20]

Here we calculate the first ten even numbers starting from one. The filter function allows us to filter desired elements from a list. It works just fine on an infinite list; it’s almost as if we just attached a predicate to it. Then we can use take to take a finite number of elements.

Again, because Haskell is lazy, it only performed the necessary work. As soon as it reached that tenth element in the output list, it stopped, because we said we only wanted the first ten elements.

Let’s take this even further. What if we want the first ten even numbers that are also divisible by eight?

> take 10 (filter (\x -> x `mod` 8 == 0) (filter even [1..]))
[8,16,24,32,40,48,56,64,72,80]

Haskell’s set of rich list operations combined with laziness can result in some pretty damn expressive code that only does the necessary work, without having to bother with loops and counters and all that fluff.

This is where cycle comes in.

> take 10 (cycle [1, 2])

[1,2,1,2,1,2,1,2,1,2]

cycle constructs an infinite list from another by repeating it… repeatedly. See where this is going? This is what is responsible for the “case alternating” behavior of spongemock. In spongemock, though, we’re giving it a list of functions:

import Data.Char

spongemock = zipWith ($) (cycle [toUpper, toLower])

Of course, this is totally allowed. We get an infinite list of functions, cycling between toUpper and toLower.

Dollar sign operator#

Okay, the last stretch now. We’re zipping together an infinite list of functions (that cycles between uppercasing and lowercasing) with our input list, and combining them with ($). But what’s ($)?

($) is function application. It is equivalent to f x:

($) :: (a -> b) -> a -> b
($) f x = f x

Haskell provides an “operator” for function application so that we can use it as a function (normal application is just a space between names–not exactly something we can refer to) and it’s also handy for nuking parentheses since it has low operator precedence.

Take this code from earlier:

> take 10 (filter even [1..])
[2,4,6,8,10,12,14,16,18,20]

It would be nice to remove those parentheses. In Haskell, function application is left-associative and has the highest priority, meaning that we are forced to use parentheses to make our intentions clear sometimes.

If we wrote this instead,

> take 10 filter even [1..]

then GHC explodes:

<interactive>:30:9-14: error:
    • Couldn't match expected type ‘[a1]’
                  with actual type ‘(a0 -> Bool) -> [a0] -> [a0]’
    • Probable cause: ‘filter’ is applied to too few arguments
      In the second argument of ‘take’, namely ‘filter’
      In the expression: take 10 filter even [1 .. ]
      In an equation for ‘it’: it = take 10 filter even [1 .. ]

<interactive>:30:1-25: error:
    • Couldn't match expected type ‘(a2 -> Bool) -> [a3] -> t’
                  with actual type ‘[a1]’
    • The function ‘take’ is applied to four arguments,
      but its type ‘Int -> [a1] -> [a1]’ has only two
      In the expression: take 10 filter even [1 .. ]
      In an equation for ‘it’: it = take 10 filter even [1 .. ]
    • Relevant bindings include it :: t (bound at <interactive>:30:1)

take is being applied with 4 arguments here, even though it should only be applied twice, at most. The “second” argument to take is a list ([a1]), but we are instead supplying the filter function, which is of type (a0 -> Bool) -> [a0] -> [a0].

With ($), we can write this:

> take 10 $ filter even [1..]
[2,4,6,8,10,12,14,16,18,20]

$ has much, much lower priority, meaning that it’s applied later–“after” take 10 and filter even [1..] in parsing. Those stay separate and parse correctly, then we apply.

Okay. Now we know everything we need to know in order to understand spongemock!

import Data.Char

spongemock = zipWith ($) (cycle [toUpper, toLower])

Take two lists: one cycling infinitely between functions that uppercase and lowercase, and the input list. Then for each pair of items, one a function and another a character, apply the function to the character. This creates the mocking spongebob effect.

Breaking it down once more:

> spongemock "waah"
"WaAh"

1. Our cycle call creates an infinite list of functions that cycle between toUpper and toLower infinitely.
2. zipWith uses ($) to apply those functions to each character in the input list, in parallel.
3. We get [toUpper $ 'w', toLower $ 'a', toUpper $ 'a', toLower $ 'h'].
4. Simplifying: [toUpper 'w', toLower 'a', toUpper 'a', toLower 'h'].
5. Simplifying: ['W', 'a', 'A', 'h'].
6. Lists of characters are strings in Haskell. So this is just: "WaAh".

I hope this article provided an effective glimpse into functional programming and what programming with Haskell is like. It’s pretty neat how it can enable us to think conceptually, in terms of infinite cycling lists instead of for loops and indexes. And due to Haskell’s laziness and syntax, you don’t miss out on performance nor terseness.