Functional isn’t always better

Oct 07 2011 Tags: , , , , ,

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.

Related articles
Enhanced by Zemanta

Related Posts

---
Need a freelance developer? Email me!

You should follow me on twitter
 Subscribe to RSS

41 responses so far

  • 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.

« Steve Jobs Crowdsourcing elegance »