HN Explorer

15 comments

[ 3.0 ms ] story [ 38.3 ms ] thread
ColinWright
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
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.

ColinWright
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.
Dn_Ab
I don't know. reirob's and fab13n's code are more general as they do not require that some type of ordering is placeable on its set of inputs.

Your code requires that the elements are comparable. So your effectively is predicated on whether you think that limitation is not a big deal (technically it greatly restricts the type of elements, practically maybe not?)

ColinWright
All true, but only serving to obscure my question about why this is not considered functional by the OP. My first thought was to go with running down the list of indices, as fab13n does, but I thought I'd go for the less generic but cleaner code to try to get to the real point.

I guess I failed.

fab13n 

    [(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
Note that this doesn't work if items is a generator.
reirob
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
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
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
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]
[deleted]
(comment deleted)
Strilanc
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_Ab
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
[deleted]
(comment deleted)