Functional isn't always better

http://swizec.com/blog/functional-isnt-always-better/swizec/2591

by Swizec • 15 years ago

13 13 15 years ago

ColinWright3• 15 years ago

Python, and assuming the given iterable of items contains no duplicates:

    def pairs_functional(items):
        return [ [a,b] \
                   for a in items \
                     for b in items \
                       if a<b \
                 ]

It does about twice as much work as necessary, but you are producing effectively unordered pairs. I haven't run any timing tests as I don't have time at the moment, but I suspect the efficiency is comparable.

I see that you are calling this an iterative solution, and then dismissing it, but it's a referentially transparent function with no side effects. Why are you saying it's not functional?

It feels to me that the algorithm you're using (zips and shifts) is simply wrong for the combination of paradigm and problem.

You can write the above to be more obviously "functional" by defining a function "cartesian product" and then filtering, but I don't really see how that's really more or less functional.

I'd be interested to see a more comprehensive explanation of what you think the problem really is, and to comments from others here on HN.

Swizec• 15 years ago

Maybe it's just my being a greenhorn talking, but I was under the impression that for loops and explicit recursion were "ugly" in functional-style code and you should instead use maps and reduces.

While my iterative solution is functional in the sense that it doesn't have any external side-effects. Internally it's still for loops and "unclean" in the sense you couldn't dissect it into a bunch of reusable functions whereas the functional solution could potentially be broken down and those lambda functions could be named and then would be re-usable.

Your python solution is very python-idiomatic though and from that standpoint therefore alright. I would probably have written something similar in python.

ColinWright3• 15 years ago

Haskell is about as functional as you can get, and the comment in http://news.ycombinator.com/item?id=3084429 and its reply contain effectively the same code.

fab13n• 15 years ago

    [(x[i],x[j]) for i in range(len(x)) for j in range(i+1, len(x))]

His problem is not with functional programming (i.e. avoiding state mutations). It is that he tries to do inductive definitions and functors in a language whose syntax is extremely unsupportive. In OCaml that would be (untested code):

    let rec pairs = function
    | a :: b -> List.map (fun x -> (a, x)) b @ (pairs b)
    | [] -> []

ezyang• 15 years ago

Note that this doesn't work if items is a generator.

reirob• 15 years ago

Maybe it come from the fact that you are using a non-functional language for functional stuff? In Haskell I'd do it like this:

  pairs[]     = []
  pairs(x:xs) =
     map (\ y -> (x,y)) (xs) ++ pairs xs

Tried, out in console:

  *Main> pairs "ABCD"
  [('A','B'),('A','C'),('A','D'),('B','C'),('B','D'),('C','D')]

It seems to do what is supposed to.

jamwt• 15 years ago

Haskell even has sugar for this via list comprehensions:

    Prelude> let pairs = "ABCD"
    Prelude> [(x, y) | x <- pairs, y <- pairs, x < y]
    [('A','B'),('A','C'),('A','D'),('B','C'),('B','D'),('C','D')]

dpatru• 15 years ago

This generates the Cartesian product and filters. (x,y) where both x and y are drawn from the original list. The previous solution only generates pairs (x, y) where y is drawn from elements after x.

FalconNL• 15 years ago

And yet another short, functional solution:

    pairs = (>>= \ ~(x:xs) -> map ((,) x) xs) . init . tails

EDIT: Or as a list comprehension:

    pairs xs = concat [map ((,) h) t | (h:t) <- tails xs]

Strilanc• 15 years ago

Adding to the list of simple implementations, here's one in C#:

    list.SelectMany((e, i) => list.Skip(i+1).Select(f => Tuple.Create(e, f)))

I think the author started with the wrong idea and didn't backtrack far enough before giving up.

Dn_Ab2• 15 years ago

The only problem here is that each time it has to skip through the entire list so far. I would write it like this in F# for equivalent generality and lazinessas yours

  let pairs sequence  = 
    sequence |> Seq.fold (fun (tailList, listOfPairs) el ->  
                let listThusFar = tailList |> Seq.map (fun x -> el, x) 
                (tailList |> Seq.skip 1), listThusFar::listOfPairs) 
                ((sequence |> Seq.skip 1),[])  
             |> snd |> Seq.concat

Functional isn't always better

Related Stories