Functional isn’t always better

Swizec Teller

I make things.

@swizec
email
github

Published
October 7, 2011
in A tech a day.

A BDSM-style collar that buckles in the back. ...

Image via Wikipedia

For a long time now I’ve been completely in love with functional programming to the point that I write functional-style code even in run of the mill normal languages.

There are many reasons I like functional code, the paper Why functional programming matters, by John Hughes sums up my opinion perfectly.

A few days ago I came upon a problem that killed my idea of functional code being superior and awesome beyond belief. This might have happened because I’m not a very good functional programmer yet, or the tool I was using (javascript) just doesn’t support the right things … but I doubt I would have written it any better in clojure.

The problem is one of turning a list of values, say, [A, B, C, D] into a list of pairs with itself, like so [[A,B], [A,C], [A,D], [B, C], [B,D], [C,D]].

Should be simple enough right? You just make another list shifted by one to the left, make a zip, then repeat until the second list is empty. This solution turns out to be horrible, looks ugly and I’m not even going to show it. So here’s my second functional solution … it’s a lot cleaner.

function pairs_functional2(data) {
    return _.reduce(_.map(_.range(1, _.size(data)),
                         function (i) {
                             return _.map(_.rest(data, i),
                                          function (item) {
                                              return [data[i-1], item];
                                          });
                         }),
                   function (memo, pairs) {
                       _.map(pairs, function (pair) {
                           memo.push(pair);
                       });
                       return memo;
                   }, []);

A little syntactic sugar wouldn’t hurt … writing a lambda in javascript isn’t the cleanest of beasts. That final reduce down there also isn’t the best of things from a functional standpoint. I don’t like that push, but honestly I didn’t know how to do that better.

Here’s an iterative solution for comparison:

function pairs_iterative(data) {
    var out = [];
    for (var i=0; i < _.size(data); i++) {
        for (var j=i+1; j < _.size(data); j++) {
            out.push([data[i], data[j]]);
        }
    }
    return out;
}

I haven’t looked at performance, but both implementations are functionally the same … I’m feeling a bit at a loss here. Am I doing something stupid in the first implementation? Or is this just the kind of problem that fits iterative programming better than functional?

I’m tempted to do an implementation in clojure just to see if this thing looks so ugly in javascript on account of the syntax …

PS: the original implementation uses underscore.js so it works in all browsers just as the iterative would. Also I don’t think javascript natively has enough such functions … it would be even uglier.

Exploration Through Example ” Blog Archive ” Further reading for “Functional Programming for Object-Oriented Programmers” (exampler.com)
What is Clojure? Who Should Use It? (drknucklehead.wordpress.com)
It’s All Functional? (drknucklehead.wordpress.com)
Fixing the callback spaghetti in node.js (github.com)
Using Custom Code to Synchronize Different Datasets (sqlserverbiblog.wordpress.com)

You should read my book, Why programmers work at night

Josh

In clojure:
(defn ordered-pairs [items]
(if (seq items) (concat (map #(vector (first items) %) (rest items))
(ordered-pairs (next items)))
[]))
Anonymous

“Functional isn’t always better”

DUH!
STEVEN SEAGAL

As far as the “syntactic sugar”… CoffeeScript would clean that up quite a bit.
http://www.invoicefox.com JankoM

var f = function(d, a, r) {
var l = d.length, x = Math.floor(a/l), y=a%l;
return a >= l*l-1 ? r : f(d, a+1, r.concat( x<y ? [[d[x],d[y]]] : [] ));
};

f([1,2,3,4], 0, []);

JSON.stringify( f([1,2,3,4], 0, []) )"[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]"
Jon Harper

Here’s a possible implementation (haskell):
f [] = []
f (x:xs) = a ++ b
where a = map (y -> [x,y]) xs
b = f xs
http://www.invoicefox.com JankoM

code got screwed by the comment system. I pasted it here: http://paste.factorcode.org/paste?id=2356
http://www.facebook.com/profile.php?id=687236189 Rany Keddo

In haskep
Guest

(distinct
(for [x stuff
y stuff :when (not (= x y))]
(sort [x y])))
http://octopusgrabbus.wordpress.com octopusgrabbus

At least a couple of recent Clojure books state that Clojure is not all about recursion, and yet there is material devoted to recursion. Those authors also state that Clojure is not all about connecting to Java functions, but the Java interaction with Clojure is quite good, and you can call a lot of useful, native Java from Clojure.

So, there is good commentary in these texts, but sometimes there is conflict by the fact things are taught, and [at least for me], you’re told don’t use what we just taught you. The only thing the Clojure texts seem to agree on is stressing that a lot of problems can be solved with sequences and sequence functions. Stuart Halloway said use recursion if you cannot solve the problem with sequence functions. I have also seen a comment that recursion is a low level fix, like assembly language?

I was told I was overthinking things by using recursion instead of sequence functions, like map. Yet, when I posted my solution with recursion, no one found fault with the program construction. My brain just “went there” to a recursive solution. Was that bad? It probably was, because my brain is still wrapping itself around using sequences and functions that manipulate them.

So, I don’t think it is all about functional is better or not, as much as it is learning a new way to handle problems. 4Clojure.com is not as good as I’d hoped for just solving sequence problems, but I’ll muddle on.

So far, Clojure’s design pragmatism choice versus being perfect or being pure sits well with me. I’ll see how my CodeLesson Clojure course goes.
http://twitter.com/demisbellot Demis Bellot

In F#:
let rec pairs = function
| h :: t -> List.append [ for i in t -> [h; i] ] (pairs t)
| _ -> []

["A"; "B"; "C"; "D"] |> pairs
http://twitter.com/SonicThud Joey

Here is a functional version in javascript that is just about as long and readable as the iterative version you have, and it doesn’t even use the underscore.js library: http://paste.factorcode.org/paste?id=2357
Pingback: Exploration Through Example » Blog Archive » Top-down design in “functional classic” programming
Slap

don’t you think you’re rushing your conclusion?
I agree with your tesis but not because your proof support them.
as Rady kenno said “[[x, y] | x <- set, y <- set, x < y]" in haskell does it.
http://www.facebook.com/profile.php?id=687236189 Rany Keddo

keep in mind that it won’t work for [1, 1, 1] because it is not a set.
Anonymous

JavaScript just kind of sucks at functional. Haskell version:
(x -> concat $ zipWith (a b -> zip (repeat a) b) x (tail . tails $ x)) ['A','B','C','D']
[('A','B'),('A','C'),('A','D'),('B','C'),('B','D'),('C','D')]

or if you prefer:
pairs_functional :: [a] -> [(a,a)]
pairs_functional x = concat $ zipWith zipper x (tail . tails $ x)
where
zipper a b = zip (repeat a) b
shaun gilchrist

Inspired by the haskell version on hn but in js:

function pairs(set) {
  return _.isEmpty(set) ? [] :
  _.map(_.rest(set), function(y){ return [_.first(set), y]})
  .concat(pairs(_.rest(set)));
}

http://jsfiddle.net/Y82we/3/
http://twitter.com/marick Brian Marick

I wrote up a solution here. I think the important question is how you think about such problems. I think about them as a relationship of facts about functions. (So I didn’t use Clojure’s `do`.)

http://www.exampler.com/blog/2011/10/07/top-down-design-in-functional-classic-programming-2/
http://activedeveloper.info mhitza

Javascript can be *flavoured* as a functional language. In Haskell:

zipPairs x = zip x ((tail x) ++ [last x])
http://activedeveloper.info mhitza

Ignore my code snippet, just skimmed your requirement and posted without realizing what you actually wanted.
http://activedeveloper.info mhitza

You could drop the prefix _. by using the “with” statement. Although it may be removed at later stages because it is not part of the strict Javascript (use strict).
Anonymous

If you want to play some code golf this can be restructured to remove the explicit recursion like so:
f = fix (g (x:xs) -> map (y -> [x,y]) xs ++ if null xs then [] else g xs)

Need to import Control.Monad.Fix for the fix function, but everything else is provided by Prelude.
Simon Belak

(combinations ‘[a b c d] 2)
http://twitter.com/kawas44 kawas

Some like it with loop… but inefficient compared to your lazy version

(defn distinct-not-ordered-pairs [coll]
(loop [[x & xs] coll, acc []]
(if (nil? x) acc
(recur xs (concat acc (for [y xs] [x y]))))))
Simon Belak

Using only core:

(defn tails [xs]
(take-while not-empty (iterate rest xs)))

(defn pairs [xs]
(mapcat (partial map vector) (map repeat xs) (rest (tails xs))))
http://ro86.myopenid.com/ XxXX

Scala can do this :
def pair(l : List[String]): List[Tuple2[String, String]] = l.size match {
case 1 => Nil
case _ => l.tail.flatMap { e => List((l.head, e)) } ++ pair(l.tail)
}
http://barak.a.pearlmutter.myopenid.com/ Barak A. Pearlmutter

{-# LANGUAGE TupleSections #-}

import Data.List (tails)

pairup1 :: [a] -> [(a,a)]
pairup2 :: [a] -> [(a,a)]
pairup3 :: [a] -> [(a,a)]
pairup4 :: [a] -> [(a,a)]
pairup5 :: [a] -> [(a,a)]
pairup6 :: [a] -> [(a,a)]
pairup7 :: [a] -> [(a,a)]

pairup1 xs = [(x,y) | (x:ys) <- tails xs, y map (x,) xs) . filter (not . null) . tails

pairup4 xs = do { (y:ys) <- filter (not . null) $ tails xs; z <- ys; return (y,z) }

pairup5 = concatMap f . tails where {f (y:ys) = map (y,) ys; f [] = []}

pairup6 [] = []
pairup6 xs@(_:xss) = concat $ do {ys <- tails xss; return $ zip xs ys}

pairup7 [] = []
pairup7 xs = concatMap (zip xs) (tails (tail xs))
Anonymous

use recur, instead else there will be a stackoverflow.
Ff

Functional isn’t always better, but for different reasons entirely. Took you long enough to discover that functional programming isn’t panacea. I’ve been torn between functional and object oriented for years now. Both have something to offer and both suffer from serious problems.
Larry

here’s an OO version in Smalltalk that doesn’t suck (and a good Smalltalker could probably do a lot better .

in := #(a b c d) asOrderedCollection.out := OrderedCollection new.in size timesRepeat: [ key := in removeFirst. in do: [ :value | out add:( Array with: key with: value). ].].
http://www.joelpm.com/ JoelPM

Erlang, just for the heck of it:
-module(combos).

-export([ combo/1 ]).

combo(List) ->
combo(List,[]).

combo([],Acc) ->
lists:reverse(Acc);
combo([H|T], Acc) ->
combo(T,permute(H,T,Acc)).

permute(X,[],Acc) ->
Acc;
permute(X,[H|T],Acc) ->
permute(X,T,[{X,H}|Acc]).
Output:
1> combos:combo([a,b,c,d]).[{a,d},{a,c},{a,b},{b,d},{b,c},{c,d}]2>
http://www.invoicefox.com JankoM

Wowo, I wrote another functional js solution of the problem today, but yours is the most beautiful JS solution by far here IMHO. I rewrote it to basic JS just for fun..
http://www.copypastecode.com/81118/
J.M.

but you mutate an array there, that’s not very functional IMHO
http://www.invoicefox.com J.M.

this was my current solution (also no mutation, but totally fugly compared to yours).
http://www.copypastecode.com/81125/
http://dissocial.st Mikhail Glushenkov

> let pairs xs = [(a,b) | ys 1, let a = head ys, b pairs "ABCD"
[('A','B'),('A','C'),('A','D'),('B','C'),('B','D'),('C','D')]

Call to length can be replaced with a O(1) check:

check a:b:_ = True
check _ = False
Mihai Lutescu

My Clojure versions:
1/ One which is just like the one you find readable. Why do you think “for” is inerently imperative? We have “for” in purelly functional contexts, like the iterative monad or “for” in Clojure is “functional” (in the meaning, there is no state mutation involved):

(defn pairs [ lst ]
(let [ n (count lst)]
   (for [i (range n)
   j (range (+ 1 i) n) ]
   [(nth lst i) (nth lst j)]))

2/ I also like the recursive version, indeed harder to grasp at a glance but which maps nicelly on it’s intuitive description: ” destructure the list in it’s head and it’s tail; concatenate all vectors obtained by repeating the head and taking each element of the tail, with the pairs obtained from the tail”
   (defn pairs [ [ head & tail ] ]
(when head
(concat (map vector (repeat head) tail)
(pairs tail))))
http://pulse.yahoo.com/_2MO6IVJDIGARGB2JTIPRHMVGFI Javier

beautiful, my version was (with same tails) :

(defn pairs [xs]
(mapcat (fn [[x & y]] (map list (repeat x) y))
(tails xs)))
http://pulse.yahoo.com/_2MO6IVJDIGARGB2JTIPRHMVGFI Javier

well i jus realized my tails is not exactly he same:

(defn tails [xs]
(take-while seq (iterate rest xs)))
Pingback: A geek with a hat » Crowdsourcing elegance
https://www.google.com/accounts/o8/id?id=AItOawkN9EVSINg-oTDAoVTD7va4e3YCAGC4thA Davide Angelocola

In clojure:

>>(defn pairs [values]
(for [x values y values :when (> (pairs [1 2 3 4])
([1 2] [1 3] [1 4] [2 3] [2 4] [3 4])
eggsyntax

It’s a moderately readable one-liner in Python:

def pairs(l):
return [(v1,v2) for i,v1 in enumerate(l) for v2 in l[i+1:]]
http://steinbitglis.myopenid.com/ Fredrik Ludvigsen

function pairs(list) { result = []; map_head = function(head, tail, index){ if (index < tail.length) { result.push([head, tail[index]]); map_head(head, tail, index+1); } }; (function cross(head, tail, index) { if (index < tail.length) { map_head(head, tail, index); cross(tail[index], tail, index+1); } })(list[0], list, 1); return result;}oh, nevermind, this is what shaun gilchrist did.

Related articles