Higher-order list operations in Racket and Haskell

matt.might.net<br>article index<br>@mattmight<br>rss

Twitter: @mattmight

Instagram: @mattmight

LinkedIn: matthewmight

Mastodon: @mattmight@mathstodon.xyz

Sub-reddit: /r/mattmight

Higher-order list operations

There is a pattern with students<br>learning functional programming.

First, they try to use loops and mutation;<br>this ends with awkward, broken programs.

There is confusion and aggravation.

Even hostility.

Eventually, they accept and embrace recursion.

But, then they write too much.

While recursion is better than iteration for<br>functional programming, new functional programmers<br>are unaware of<br>powerful libraries to encapsulate recursion over<br>common data structures like lists.

This post explains some of the common<br>higher-order list operations in Racket and Haskell<br>by re-implementing them.

To start, I abstract mapping out of adding and substracting to lists, and<br>then I abstract folding and reducing out of mapping.

Just as with mutation, students are slow to give up<br>on conditionals as well, but they eventually accept<br>pattern-matching in its place.

To contrast the expressiveness in conditionals and pattern-matching,<br>I've implemented some functions<br>in both styles.

Where possible, I have also demonstrated<br>each list operation using Racket's and Haskell's<br>comprehension notations.

The post concludes with a brief example of using<br>continuation-passing style<br>to simplify multi-return-value<br>list operations like zip and partition.

Read on for more.

Adding and subtracting one

Suppose you want to add one to every element of a list.

For programmers new to functional programming,<br>it's tempting to write a recursive function for this:

; Racket:<br>(define (add1 lst)<br>(if (null? lst)<br>'()<br>(cons (+ 1 (car lst))<br>(add1 (cdr lst)))))

(add1 '(1 2 3))

-- Haskell:<br>add1 :: [Int] -> [Int]<br>add1 lst =<br>if null lst<br>then []<br>else (head lst + 1) : (add1 (tail lst))

Now suppose you want to sustract one from every<br>element of a list.

Following the same strategy as before, you would<br>create a new recursive function:

; Racket:<br>(define (sub1 lst)<br>(if (null? lst)<br>'()<br>(cons (- (car lst) 1)<br>(sub1 (cdr lst)))))

; Haskell:<br>sub1 :: [Int] -> [Int]<br>sub1 lst =<br>if null lst<br>then []<br>else (head lst - 1) : (sub1 (tail lst))

While both add1<br>and sub1<br>are functionally correct,<br>it is easier to use map:

; Racket:<br>(map (&lambda; (x) (+ x 1)) '(1 2 3)) ; yields '(2 3 4)

; Haskell:<br>map (+1) [1,2,3] -- yields [2,3,4]

Abstracting into map

We can coax the definition of<br>map out of<br>add1 by<br>abstracting the addition operation into a<br>functional parameter, f:

; Racket:<br>(define (map/test f lst)<br>(if (null? lst)<br>'()<br>(cons (f (car lst))<br>(map/test f (cdr lst)))))

; Haskell:<br>mapTest :: (a -> b) -> [a] -> [b]<br>mapTest f lst =<br>if null lst<br>then []<br>else (f (head lst)) : (mapTest f (tail lst))

(I'm not using the name map to avoid<br>clashing with the language-provided map.)

Map with matching

While the prior definition of map is acceptable,<br>it is not the most natural way to express it in functional<br>programming languages.

Functional programmers prefer<br>structural pattern matches over explicit conditional tests:

; Racket:<br>(define (map/match f lst)<br>(match lst<br>['() '()]<br>[(cons hd tl) (cons (f hd) (map/match f tl))]))

; Haskell:<br>mapMatch :: (a -> b) -> [a] -> [b]<br>mapMatch f [] = []<br>mapMatch f (hd:tl) = (f hd):(mapMatch f tl)

Mapping with comprehensions

Racket provides special for forms (comprehensions)<br>which can often replace uses of higher-order list operations<br>like map.

For example, to add one to every list element, try:

(for/list ([x '(1 2 3 4 5)])<br>(+ x 1)) ; yields '(2 3 4 5 6)

Haskell also provides a comprehension notation for lists:

[ x + 1 | x

Filtering lists

The filter function offers another chance to<br>see the difference between explicit conditional tests<br>and structural pattern matching.

The filter function returns a list<br>in which every element satisfies a predicate:

; Racket:<br>(define (filter/test p? lst)<br>(cond<br>[(null? lst) '()]<br>[(p? (car lst)) (cons (car lst)<br>(filter/test p? (cdr lst)))]<br>[else (filter/test p? (cdr lst))]))

-- Haskell:<br>filterTest :: (a -> Bool) -> [a] -> [a]<br>filterTest p lst =<br>if null lst<br>then []<br>else if (p (head lst))<br>then (head lst) : (filterTest p (tail lst))<br>else<br>(filterTest p (tail lst))

or, with structural pattern matching:

; Racket:<br>(define (filter/match p? lst)<br>(match lst<br>['() '()]<br>[(cons (? p?) tl) (cons (car lst) (filter/match p? tl))]<br>[(cons hd tl) (filter/match p? tl)]))

; Haskell:<br>filterMatch :: (a -> Bool) -> [a] -> [a]<br>filterMatch p [] = []<br>filterMatch p (hd:tl) | p hd = hd:(filterMatch p tl)<br>| otherwise = filterMatch p tl

With these:

; Racket:<br>(filter/match even? '(1 2 3 4 5 6)) ; yields '(2 4 6)

-- Haskell:<br>filterMatch even [1,2,3,4,5,6] -- yields [2,4,6]

Filtering with comprehensions

Racket's for forms accept predicates<br>to allow fusion of mapping and filtering:

For example, to select the odd elements and add one:

(for/list ([x '(1 2 3 4 5)]<br>#:when (odd? x))<br>(+...