Take the 2-minute tour ×

What are your favourite short, mind-blowing snippets in functional languages?

My two favourite ones are (Haskell):

powerset = filterM (const [True, False]) 

foldl f v xs = foldr (\x g a -> g (f a x)) id xs v -- from Hutton's tutorial

(I tagged the question as Haskell, but examples in all languages - including non-FP ones - are welcome as long as they are in functional spirit.)

share|improve this question
To a C++ coder, that looks like a bunch of identifiers with some punctuators thrown in for good measure :-P –  Nick Bedford Oct 7 '09 at 0:05
@Nick Bedford: Oh, I was thinking a cat walked on the keyboard. –  Powerlord Oct 7 '09 at 17:12
@Ellery: It's the same as the normal foldl: (a -> b -> a) -> a -> [b] -> a. The first argument is a function that takes an accumulator and a list element and returns a new value for the accumulator. The second argument is the initial accumulator value. The third argument, obviously, is the list. –  Chuck Oct 11 '09 at 19:13
Oh I get it. id is the initial value you pass to foldr, so foldr is composing functions and you end up with a function which is what v gets applied to. And the function composition turns out to be exactly the same as foldl. That's crazy. Can you implement foldr in terms of foldl? I think I'm going to try my hand at this stuff... –  Ellery Newcomer Oct 12 '09 at 1:17
Ha! I got it! foldr f v xs = foldl (\g x b -> f x (g b)) id xs v –  Ellery Newcomer Oct 12 '09 at 2:40
show 8 more comments

22 Answers

up vote 17 down vote accepted
bwp xs = map snd $ sort $ zip (rots xs) (rrot xs)
rots xs = take (length xs) (iterate lrot xs)
lrot xs = tail xs ++ [head xs]
rrot xs = last xs : init xs

The (forwards) Burrows-Wheeler Transform, from a Functional Pearl paper. BWT is used as the second stage in the bzip2 compression (after run-length encoding), grouping similar features together to make most inputs more compressible by the following stages.

The paper also has a couple implementations for the inverse, also elegant but not quite as short.

share|improve this answer
That's awesome. –  David Crawshaw Oct 11 '09 at 21:02
What do you think about this re-factoring of the above: bwp xs = map snd $ sort $ zip (tail $ iterate lrot xs) xs where lrot (a:as) = as ++ [a] ;-) –  jberryman Nov 7 '09 at 21:26
Isn't that longer than the array-based Array.sort [|for i in 0..n-1 -> [|for j in 0..n-1 -> xs.[(i+j) % n]|]|] |> Array.map (fun xs -> xs.[n-1])! –  Jon Harrop May 25 '10 at 3:01
This is making quite unwise use of lists, by the looks of it... if you want to append like that, Data.Sequence from the containers package is probably better. –  Ben Millwood Sep 4 '12 at 23:02
add comment

My "aha!" moment with JavaScript came when I was reading this memoization blog post. The relevant functional code, from that post was:

Bezier.prototype.getLength = function() {
  var length = ... // expensive computation
  this.getLength = function(){return length};
  return length;

Basically, the function overwrites itself with the answer after the first computation, make all subsequent calls memoized.

It was at this point that I realized how all my previous ill-conceived notions of JS were founded in ignorance. And it was at this point that I realized the true power of its functional aspects.

share|improve this answer
+1 for teh mighty power of JS –  annakata Oct 12 '09 at 19:26
not forcing the callers to be aware of and have to pre-test for the memoization is a real advantage. –  PanCrit Oct 13 '09 at 17:03
this looks more like a clever use of a dynamic language feature than anything fundamentally "functional", however clever. (I do think it's cool, though :) –  JB. Oct 13 '09 at 19:09
Indeed, this "feature" requires mutability -- something functional programs try to avoid or partition off into its own sandbox. –  ephemient Oct 14 '09 at 21:43
That's business as usual in Haskell :) –  ephemient Oct 19 '09 at 16:28
show 6 more comments

My mind-blowing time happened while watching the SICP video lectures.
Data made of thin air. The functions as data containers.

More specifically, store a pair of data even if the language doesn't have a built-in data container.
That was my baptism on functional programming.

#lang scheme

;; Version 1    
(define (pair x y)
  (lambda (p)
    (cond ((> p 0) x)
          (else y))))

(define (pair-x z)
  (z 1))

(define (pair-y z)
  (z 0))

;; Version 2, Alonzo Church Pairs - Lambda Calculus
;; SICP exercise
(define (church-pair x y)
  (lambda (m) (m x y)))

(define (church-pair-x z)
  (z (lambda (x y) x)))

(define (church-pair-y z)
  (z (lambda (x y) y)))


> (define p (pair 7 8))
> (pair-x p)
> (pair-y p)
share|improve this answer
Indeed, absolutely wonderful. –  Ionuț G. Stan Oct 13 '09 at 8:54
C# implementation: diditwith.net/2008/01/01/BuildingDataOutOfThinAir.aspx –  Juliet Oct 13 '09 at 13:21
@Juliet, thanks for the link. For those who have the SICP, the code I posted is in chapter 2.1.3 What Is Meant By Data? –  Nick Dandoulakis Oct 13 '09 at 15:45
It's mentioned on "lecture 2b: Compound Data.avi", at 01:03:44. –  Nick Dandoulakis Oct 13 '09 at 15:57
add comment

I got this from Sean Seefried. Here we use tying the knot to replace all leaves of a tree with the minimal leaf value in a single pass.

data Tree
  = Fork Tree Tree
  | Leaf Int

aux i (Leaf i') = (i', Leaf i)
aux i (Fork t1 t2) =
  let (m1, t1') = aux i t1
      (m2, t2') = aux i t2
  in  (min m1 m2, Fork t1' t2')

replaceMin t =
  let (m, t') = aux m t in t'


replaceMin (Fork (Leaf 4) (Leaf 7)) = Fork (Leaf 4) (Leaf 4)
share|improve this answer
"Tying the knot" is the standard name, at least in the Haskell community, for the general case of Michael Steele's "I'm always impressed when I see Haskell functions that feed part of their output into the input of the same function". This is a nice example :) –  ephemient Oct 11 '09 at 15:58
add comment

Definitely this one (from wikipedia) for a short RPN-interpreter.

calc = foldl f [] . words
    f (x:y:zs) "+" = (y + x):zs
    f (x:y:zs) "-" = (y - x):zs
    f (x:y:zs) "*" = (y * x):zs
    f (x:y:zs) "/" = (y / x):zs
    f xs y = read y : xs

And to bring a slightly more complicated example ;-): Linq raytracer

share|improve this answer
add comment

I've always loved the Fibonacci numbers definition:


Or anything else co-recursive.

share|improve this answer
add comment

If C++ metaprogramming counts, I choose the first metaprogram ever created :)

// Prime number computation by Erwin Unruh

template <int p, int i> struct is_prime {

template < int i > struct Prime_print {
    Prime_print<i-1> a;

#ifndef LAST
#define LAST 10
main () {
    Prime_print<LAST> a;
share|improve this answer
I was looking at that, thinking "that can't possibly compile, can it?" Sadly, even updating it to modern C++ (template<> struct), GCC refuses to compile this satisfactorily. –  ephemient Oct 6 '09 at 18:05
@ephemient Believe me, this code was written NOT to compile. It prints prime numbers in the compilation error msgs ;) see the site for the produced error msgs by a C++ compiler. –  AraK Oct 6 '09 at 18:08
Yes, but GCC halts on the very first D<2> in struct Prime_print<2> and doesn't go any further, which kind of defeats the purpose of the rest of the program, and I'm not sure how to convince GCC to behave more like the writer wanted it to. –  ephemient Oct 6 '09 at 19:41
@ephemient This isn't really standard C++. This code was written ~15 years ago, there wasn't standard C++ that time. It needs some modifications so it becomes a standard one. eg. (main -> int main), (full specialization is little different in standard C++). Maybe I'll try to write a standard version just for fun :) –  AraK Oct 6 '09 at 20:16
Hey, I do realize that! Hence my first comment about template<>, since the syntax for template specialization has changed. However, the problem is that in order for this to work, you need the compiler to blow up while chasing Prime_print<LAST> instead of on Prime_print<2> a few lines up, and GCC just refuses to cooperate... –  ephemient Oct 6 '09 at 20:33
show 1 more comment

The biggest "Oh Wow!" moment I've had is with the exponentiation function in lambda calculus.


results in a ^ b

share|improve this answer
how so? if the lambda calculus, juxtaposition is function application, so this is the flip function. How do you get exponentiation? –  ja. Oct 13 '09 at 9:19
It has to do with the way numbers are defined in lambda calculus. \ab.b = 0, \ab.ab = 1, \ab.a(ab) = 2, etc –  Ellery Newcomer Oct 13 '09 at 17:29
@ja, \ab.ba is not flip, it is flip id. flip = \fab.(fb)a, which is very different. id = \ab.ab = 1 in Church numerals. (Which is expected, since function composition is multiplication of Church numerals.) –  misterbee Jan 3 at 5:58
add comment

C++ is to pointers as functional programming is to continuations: newbies are mystified by them both.

Start with a simple binary tree insert:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec insert x = function
    | Nil -> Node(Nil, x, Nil)
    | Node(l, a, r) as node ->
        if x > a then Node(l, a, insert x r)
        elif x < a then Node(insert x l, a, r)
        else node

Simple, utilitarian, but its not tail-recursive. So, you go-go-gadget continuation passing style, and you get this:

let insert x tree =
    let rec loop cont x = function
        | Nil -> cont <| Node(Nil, x, Nil)
            if x > a then loop (fun r' -> cont <| Node(l, a, r')) x r
            elif x < a then loop (fun l' -> cont <| Node(l', a, r)) x l
            else cont node
    loop id x tree

At the expense of a little clarity, the algorithm is properly tail-recursive.

Here's a traditional and tail-recursive list append side-by-side:

let rec append a b =
    match a with
    | [] -> b
    | x::xs -> x::append xs b

let append2 a b =
    let rec loop cont = function
        | [] -> cont b
        | x::xs -> loop (fun xs' -> cont <| x::xs') xs
    loop id a
share|improve this answer
Just for fun, compare "append [1M .. 60000M] [1M]" to "append2 [1M .. 60000M] [1M]": the first function throws a stack overflow exception, the other completes successfully. –  Juliet Oct 13 '09 at 14:13
add comment

As noted by Ron Jeffries on his blog

#define pi 3.14159

//z = radius
//a = thickness
float volume (float a, float z) { return pi*z*z*a; }
share|improve this answer
And if you remove the points, it's still interesting: v = (. ((*) =<< (pi *))) . (*) –  jrockway Oct 11 '09 at 19:20
what is functional about this? It's just a c function returning the volume –  Toad Oct 14 '09 at 7:06
It's intended to be humerous. It's not clever, but it is functional. jrockway's spin on it is actually clever. –  DaveParillo Oct 15 '09 at 13:43
add comment

Courtesy of Douglas Crockford:

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);

And the inevitable application:

var factorial = Y(function (fac) {
    return function (n) {

var number120 = factorial(5);

For more exploration of the fine line between clever and stupid, see Evolution of a Haskell Programmer.

share|improve this answer
add comment


As a contrived example, I'll show how to find the mean average of a list.

This basic example requires 2 traversals through the list:

average_basic :: [Double] -> Double
average_basic xs = sum xs / length xs

This example leverages the power of lazy evaluation to feed part of the results of a function back into the function call itself:

average :: [Double] -> Double
average xs = s
  -- avg calculates the length of a list, then feeds that result back into itself
  -- to total up the average number.
  where (s, len) = avg len xs

-- Given the length of a list, scan through it calculating the average and length
-- along the way.
avg :: Double -> [Double] -> (Double, Double)
avg len xs = foldl' op (0, 0) xs
  where op (res, l) x = (res + x / len, l + 1)

example run:

Prelude> :m +Data.List
Prelude Data.List> let avg len xs = foldl' op (0, 0) xs where op (res, l) x = (res + x / len, l + 1)

Prelude Data.List> let average xs = s where (s, len) = avg len xs
Prelude Data.List> average [1..10]
Prelude Data.List>
share|improve this answer
The problem with doing it this way is that floating point inaccuracies add up... it does look more clever than the more obvious average xs = s / fromInteger l where (s, l) = foldl' (\(!s, !l) x -> (s+x, l+1)) (0, 0) xs, though. –  ephemient Oct 9 '09 at 4:13
add comment

this is the scheme implementation of the omega combinator (essentially an infinite loop):

share|improve this answer
add comment

Calculating the list of all Fibonacci numbers, lazily. Code snippet written in Scala.

class ConsStream[T](str: => Stream[T]) {
  def ::(element: T) = Stream.cons(element, str)

implicit def stream2ConsStream[T](str: => Stream[T]) = new ConsStream[T](str)

lazy val fib: Stream[BigInt] = 0 :: 1 :: fib.zip(fib.tail).map(n => n._1 + n._2)

This can be made shorter (but not as nice) without using the implicit conversion that adds the :: operator to a Stream, by writing

lazy val fib: Stream[BigInt] = 
  Stream.cons(0, Stream.cons(1, fib.zip(fib.tail).map(n => n._1 + n._2)))

-- Flaviu Cipcigan

share|improve this answer
Over in Haskell-land, we'd write this simply as fib = 0 : 1 : zipWith (+) fib (tail fib) –  ephemient Oct 6 '09 at 22:17
@ephemient: Using Scala 2.8 and zipWith from Scalaz, the above Scala code gets compressed to: lazy val fib: Stream[BigInt] = 0 #:: 1 #:: (fib zipWith fib.tail)(_ + _). Longer than the Haskell version, but much shorter than the original Scala version :) –  missingfaktor Aug 21 '10 at 9:03
add comment

After reading Steven Huwig's post about a Javascript Y-Combinator I played around a bit with that idea. A simpler version of the Y-combinator would be this:

function Y(f) {
  return function recf(n) {
    return f(recf, n);

This gives an easy implementation of the factorial function:

function facstep(rec, n) {
  if (n==0)
    return 1;
  return n * rec(n-1);

var fac = Y(facstep);


The syntax for this can be simplified even more. By using some of Javascripts special features the recursive step can be passed implicitly as this while supporting any number of arguments for the "recursive" function:

function Y(f) {
  return function rec() {
    return f.apply(rec, arguments);

function gcdstep(n, m) {
  // greatest common divisor
  if (n == m)
    return n;
  if (n > m)
    return this(n-m, m);
    return this(m, n);

var gcd = Y(gcdstep);
alert(gcd(350, 40));

This syntax looks quite straight forward, but note that it's not normally possible for a Javascript function to refer to itself by using this, this normally refers to the object the function is a method of. In this case this references the function itself, due to the magic of the Y-combinator:

share|improve this answer
Your fixed point combinator seems to break the spirit of it since it is dependent on recursion (you are having a function pass a reference to itself along). The Steven Huwig one you linked to does not do this. –  Matthew Manela Oct 15 '09 at 5:08
It's based on the Haskell style y f = f (y f), which also uses some kind of recursion. I also wanted to avoid the additional function wrapper you easily end up with if you try to emulate Haskells laziness. –  sth Oct 19 '09 at 6:27
add comment

Breadth-first traversal of an n-ary tree in Haskell:

bfs t = (fmap . fmap) rootLabel $
          takeWhile (not . null) $
            iterate (>>= subForest) [t]
share|improve this answer
add comment

Hamming numbers in Haskell.

hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
     where merge (x:xs) (y:ys)
            | x < y     = x : merge  xs  (y:ys)
            | y < x     = y : merge (x:xs)  ys
            | otherwise = x : merge  xs     ys

This generalizes very elegantly to a solution generating any sort of smooth numbers. See a very long discussion at this lambda-the-ultimate thread: http://lambda-the-ultimate.org/node/608

share|improve this answer
add comment


Given 4 number a, b, c, and d; output the sequence of a, b and c along with arithmetic
operators such that the result is d. The arithmetic operations allowed are 

I/p:    a,b,c,d
O/p:    <expression>
        I/p:    4        3      2       10
        O/p:    4+3*2=10

Solution: (in Scala)

object Aha {
  def main(args: Array[String]) {
    val (a, b, c, d) = (readInt, readInt, readInt, readInt)
    val operations = List[((Int, Int) => Int, Int, String)](
      ({_+_}, 1, "+"), ({_-_}, 1, "-"), ({_*_}, 2, "*"), ({_/_}, 2, "/")
    for {
      (i, pi, si) <- operations
      (j, pj, sj) <- operations
      if((pi >= pj && j(i(a, b), c) == d) || (pi < pj && i(a, j(b, c)) == d))
    } println(a + si + b + sj + c + "=" + d)

Same thing in C++ (with Boost):

#include <iostream>
#include <string>
#include <functional>

#include <boost/tuple/tuple.hpp>
#include <boost/function.hpp>
#include <boost/foreach.hpp>

using namespace std;
using namespace boost;

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  tuple<function<int(int, int)>, int, string> operations[] = {
    make_tuple(plus<int>(), 1, "+"),
    make_tuple(minus<int>(), 1, "-"),
    make_tuple(multiplies<int>(), 2, "*"),
    make_tuple(divides<int>(), 2, "/")
  function<int(int, int)> i, j;
  int pi, pj;
  string si, sj;
  BOOST_FOREACH(tie(i, pi, si), operations) {
    BOOST_FOREACH(tie(j, pj, sj), operations) {
        cout << a << si << b << sj << c << "=" << d << endl;
share|improve this answer
add comment

My personal favourite is the recursive directory traversal function from Higher Order Perl. It was my first introduction to the power of functional programming (in this case the complete decoupling of the file tree traversal from the specific closures that act on the files and directories), and it really blew me away.

sub dir_walk {
   my ( $top, $file_func, $dir_func ) = @_;
   my $dh;

   if ( -d $top ) {
      my $file;
      unless ( opendir $dh, $top ) {

      my @results;
      while ( $file = readdir $dh ) {
         next if $file eq '.' || $file eq '..';
         push @results, dir_walk("$top/$file", $file_func, $dir_func);

      return $dir_func ? $dir_func->($top, @results) : ();      
   else {   
      return $file_func ? $file_func->($top): ();      
share|improve this answer
add comment

After reading about Haskell's currying capabilities, I said to myself: "I can do that in JavaScript". I did it and am very proud of it (hence this answer). The whole gist is on GitHub, but here goes:

var curry = function (f) {
    var array = Array.slice,
        prevArity = arguments[1] || f.length;

    return function () {
        var args = array(arguments),
            currArity = args.length;

        if (currArity >= prevArity) {
            return f.apply(this, args);

        return curry(function () {
            return f.apply(this, args.concat(array(arguments)));
        }, prevArity - currArity);

And these are some BDD specs for it:

$.describe("The curry() function", function () {
    $.it("should curry one argument functions", function () {
        var unary = curry(function (a) {
            return a;

        var result = unary(1);


    $.it("should curry multi argument functions", function () {
        var nary = curry(function (a, b) {
            return a + b;

        var result = nary(1)(2);


        var nary = curry(function (a, b, c) {
            return a + b + c;

        var result = nary(1, 2)(3);

share|improve this answer
add comment

I like Duff's Device:


This is essentially a loop unrolled custom memcpy, as opposed to the more straightforward implementation:


this version has ~8 times the number of comparisons, decrements and jumps.

You probably woudn't want to do something like this in the place of just using memcpy in most circumstances. I actually had call to use a similar construct recently to interleave some arrays and measured a fairly nice speed increase.

share|improve this answer
how is this functional? –  Scott Weinstein Oct 14 '09 at 21:26
Do you mean What does it do? or how does it work? or how does it compile, or something else? –  Dolphin Oct 14 '09 at 21:43
@Dolphin, functional code does not mean code that is functioning (as in compiles or whatever), but code that respects the functional programming paradigm. en.wikipedia.org/wiki/Functional_programming –  Ionuț G. Stan Oct 14 '09 at 21:47
HA! that is what I get for not reading the post and misreading the title. I kind of wondered why everyone was posting answers in functional languages. –  Dolphin Oct 14 '09 at 21:50
add comment

I am still newb in functional, spent like 20 hours learning it, but i like this code and lazines

orderf :: Integer -> Integer -> Integer -> Integer
orderf 1 c b  =(c + b)
orderf d c b  = ( foldl (orderf (d - 1) ) c (replicate' (b - 1) c) )

-- orderf 1 7 9 -- 7 + 9
-- orderf 2 7 9 -- 7 * 9
-- orderf 3 7 9 -- 7 ^ 9
-- orderf 4 7 9 -- 7 ^ 7 ^ 7 ^ 7 ^ 7 ^ 7 ^ 7 ^ 7 ^ 7  but do not try this
-- orderf 3 99 99 ok, this works 
share|improve this answer
add comment

Your Answer


