0

I've been trying to compare two lists in Haskell and found an answer here.

I wonder how all (flip elem listx) input works, especially for the role flip plays here.

When I take out flip it won't work anymore.

ggorlen
  • 44,755
  • 7
  • 76
  • 106
manuzhang
  • 2,995
  • 4
  • 36
  • 67
  • 5
    Note: I suspect this would be idiomatically written: ``all (`elem` listx) input``. If you know about backticks and operator sections this should make sense. – luqui Oct 01 '11 at 08:54
  • But why elem is an infix here? – manuzhang Oct 01 '11 at 11:21
  • Any function with at least 2 arguments can be used in infix form. And because `e ´elem´ list` just reads better than `elem e list` many prefer it this way. – Ingo Oct 01 '11 at 11:31
  • but the two arguments are listx and input? so isn't it a prefix notation here? – manuzhang Oct 01 '11 at 13:50
  • `input` isn't an argument to `elem`, quite. Read left to right. `all` takes two arguments, a function and a list, and returns true if the function is true for everything in the list. The arguments to elem are listx and one element at a time from input. – Zopa Oct 01 '11 at 16:03
  • The complexity of your solution is O(n²), wouldn't something like `sort listx == sort input` be preferrable, for O(n log n) complexity? – valderman Oct 01 '11 at 18:05
  • @Zopa, yeah, but what's puzzled me is whether it's a infix notation here where a backtick is needed – manuzhang Oct 03 '11 at 14:23
  • @valderman, thx for advice! I'm new to Haskell and functional programming so efficiency is not my concern for the current – manuzhang Oct 03 '11 at 14:24

1 Answers1

9
  1. flip elem listx is equivalent to (flip elem) listx.
  2. (flip elem) is the same as elem, but with the arguments in opposite order. This is what flip does.
  3. elem is a function that takes an element and a list, and checks whether the element belongs to the list.
  4. So flip elem is a function that that takes a list and an element, and checks whether the element belongs to the list.
  5. Therefore flip elem listx is a function that that takes an element, and checks whether the element belongs to listx.
  6. Now all takes a predicate and a list, and checks whether all elements of the list satisfy the predicate.
  7. all (flip elem listx) take a list, and checks whether all elements of the list satisfy flip elem listx. That is, whether they all belong to listx.
  8. all (flip elem listx) input checks whether all elements of input belong to listx.
  9. Q.E.D.
n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243
  • @n.m. I found the type of flip on [Hoogle](http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:flip)`flip :: (a->b->c)->b->a->c`which makes me to believe it is `a elem listx` supposing a is an element of input. It makes sense now why flip is needed here and I have to use backtick without it – manuzhang Oct 14 '11 at 01:48