4 ms·
Functional isn't always better
- ColinWright 15y agoPython, 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 15y agoMaybe 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 15y agoHaskell is about as functional as you can get, and the comment in http://news.ycombinator.com/item?id=3084429 http://news.ycombinator.com/item?id=3084429 and its reply contain effectively the same code.
- Dn_Ab 15y agoI 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 15y agoAll 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 15y 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 15y agoNote that this doesn't work if items is a generator.
- reirob 15y agoMaybe 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 15y agoHaskell 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 15y agoThis 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 15y agoAnd 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 15y ago[deleted]
- Strilanc 15y agoAdding 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 15y agoThe 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 15y ago[deleted]