Functional isn't always better(swizec.com)

13 pointsby Swizec15 lat temu13 comments

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

5 comments

reirob15 lat temu

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.

FalconNL15 lat temu

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]

jamwt15 lat temu

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')]

dpatru15 lat temu

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.

ColinWright15 lat temu

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.

fab13n15 lat temu

    [(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)
    | [] -> []

ezyang15 lat temu

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

Swizec15 lat temu

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.

ColinWright15 lat temu

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_Ab15 lat temu

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?)

ColinWright15 lat temu

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.

Strilanc15 lat temu

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_Ab15 lat temu

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]15 lat temu