Implicit Recursion

September 5, 2023

I recently started learning Haskell, and I came across a structure in the language that really made me think: Currying. Consider a function called “add” that takes two integers and returns an integer. Here’s the function signature in C:

int add(int a, int b);

And in Haskell:

add :: Int -> Int -> Int

If you’re not familiar with Haskell, the above signature probably doesn’t seem very intuitive. The “->” operator in this context is right-associative; we can add parenthesis to more clearly show what’s happening.

add :: Int -> (Int -> Int)

In plain English, you might describe it like this: “add is a function that receives an Int and returns a function which receives and returns an Int”. So really, under the hood, the “add” function doesn’t accept two arguments; it rather accepts a single argument and returns another function which accepts the second and returns the final result. So when we call the function:

add 1 2

“add 1” is executed (“add” is called with a single argument), and returns a nameless (Int -> Int) function¹, which is then called with the single Int argument 2, which yields the result of 3.

This is really cool, because, besides writing the signature, the programmer doesn’t need to worry about this inherently recursive nature of functions unless they want to: the implementation of add is completely intuitive:

add a b = a + b

and, as written above, add can be called as if it received two arguments, even though it actually only receives one, because the syntactical rules of Haskell are laid out in such a way that happens to allow this ².

But how is this useful? Functions are ubiquitous in Haskell: they are passed and returned very frequently; such functions are often simple variations or partial applications of built-in functions, so it’s natural to simply pass/return a partially applied function instead of making a unique function (or lambda) that encapsulates that behavior. The following are examples³.

-- add 5 to each element of `list'
map ((+) 5) list

-- function that adds 5 to each element of `list'
addFive :: [Int] -> [Int]
addFive = map ((+) 5)
-- map is of type `(a -> b) -> [a] -> [b]', where a and b are generic types;
-- passing `((+) 5)' (of type `Int -> Int') to map yields a function of type
-- `[Int] -> [Int]', which is the desired return-type
-- functions can also directly take arguments (see below), but this
-- example shows that returning a function that takes those same arguments
-- has the same effect
alternateAddFive :: [Int] -> [Int]
alternateAddFive l = map ((+) 5) l

-- removes elements from `names' that contain the character 'z'
filter (not . elem 'z') names
-- the '.' operator is "pipe"; it returns the left-hand-side applied on (called with)
-- the result of the function on the right-hand-side

-- sum the odd-indexed elements of each row of 2d `list'
map (sum . map snd . filter (odd . fst) . zip [0..]) list

-- element-wise addition of the 2d lists `a' and `b'
zipWith (zipWith (+)) a b

Sections

While Currying adds lots of flexibility in when the arguments are applied, it is inflexible when it comes to the order in which they are applied (the first argument must be passed first). Haskell has a feature called “sections” which allow binary functions to apply their arguments in an arbitrary order.

-- divide each element of `list' by 2
map (/2) list

-- convert each element of `list' to its reciprocal
map (1/) list
-- (this is equivalent to)
map ((/) 1) list

-- remove vowels from `chars'
filter (not . (`elem`"aeiou")) chars
-- the backticks convert the function `elem' into an infix operator

C <=> Haskell

This probably sounds like a long-shot, but the implicit nature of Currying struck me as quite similar to a very common syntactical mechanism in a much-less-esoteric language, C, and many of its descendants. This is probably really obvious to some, but I didn’t realize it until a few months ago, and I have yet to come across a teaching resource that points this out. If you don’t already know what it is, I’d encourage you to try to think of it before you scroll past this hilarious Haskell meme.

There is no special notion of “else if” in C: “else if” is literally a termination of an else-clause followed by an immediate beginning of another if-statement. The following code-blocks are syntactically identical except for indentation and optional braces.

if(a) {
    /* block a */
} else if(b) {
    /* block b */
} else if(c) {
    /* block c */
} else {
    /* block d */
}

if(a) {
    /* block a */
} else {
    if(b) {
        /* block b */
    } else {
        if(c) {
            /* block c */
        } else {
            /* block d */
        }
    }
}

Another way of saying it: an if-else statement accepts exactly two clauses, however, if the second clause is another if-else statement, then the illusion (and effect) of a multi-clause if-statement can be made.

This sounds awfully similar to Currying.

f a b c d

(((f a) b) c) d