-3

Here are some equations; at least one of them is false. Which are the true ones, and which are false?

map f . take n    = take n . map f
map f . reverse   = reverse . map f
map f . sort      = sort . map f
map f . filter p  = map fst . filter snd . map (fork (f,p))
reverse . concat  = concat . reverse . map reverse
filter p . concat = concat . map (filter p)

Justify your answer for each with an example.

Its a question I got in my assignment. I checked all the equations but all the equations are coming true. I can't find any test case in which any equation is false. Please help me find the equation which is false

6
  • 6
    You might want to broaden your choices for your f test function. Did you try something like the sine function for example ?
    – jpmarinier
    Mar 18 at 13:12
  • Some list functions like reverse operate on lists of arbitrary types. Others don't, like sum that operates only on lists of numbers. The latter case is suspicious, and indeed it would break equations like f . sum = sum . map f. Try seeing if there are similarly suspicious functions in your homework text.
    – chi
    Mar 18 at 13:29
  • 2
    What does "checked" mean in this context? You're supposed to decide, for example, if map f . sort = sort . map f is true for all functions f, not just find a function f for which it is true. (Either it's true for all f, or you can find an f for which it is not true.)
    – chepner
    Mar 18 at 14:23
  • One of your 6 equations can be expressed in plain English by a sentence like: “Function f has the xyz property”. Once you have figured out which of the 6 equations that is, you just need to find one function f that does not have the xyz property.
    – jpmarinier
    Mar 18 at 14:46
  • 3
    That's your job. But I will say, there are trivial functions for which map f . sort = sort . map f does not hold.
    – chepner
    Mar 20 at 12:06

1 Answer 1

0

Please consider the third equation:

map f . sort  =  sort . map f

In plain English, it means that going thru function f can be done equivalently before or after sorting the input list. Hence, function f is order preserving, or equivalently: increasing.

So let's peak a function that is not increasing. For example library function negate which multiplies its input by minus one.

Testing:

$ ghci
GHCi, version 8.10.7: https://www.haskell.org/ghc/  :? for help
...
 λ> 
 λ> import Data.List (sort)
 λ> 
 λ> negate 4
 -4
 λ> 
 λ> negate (-3)
 3
 λ> 
 λ> (map negate . sort) [1,2,3]
 [-1,-2,-3]
 λ> 
 λ> (sort . map negate) [1,2,3]
 [-3,-2,-1]
 λ> 
 λ> (sort . map negate) [1,2,3] == (map negate . sort) [1,2,3] 
 False
 λ> 

So we have found our counter-example, as required by the rules of the game.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.