How to use function composition for applying a function to first elements of a list?

Recall that . (composition) is defined as:

f . g = \x -> f (g x)

That is, it composes two functions of one argument each. The result (another function of one argument) passes its argument x to g, and the result of that to f.

Your first attempt was:

map (subtract 1) . take
-- inline the definition of (.)
--   with f = map (subtract 1)
--   and g = take
\x -> map (subtract 1) (take x)

This doesn't work because map expects a list as its second argument, but take x is not a list. (It is a function mapping lists to lists, [a] -> [a].)

Your second attempt:

map (subtract 1) . take n
-- inline the definition of (.)
--   with f = map (subtract 1)
--   and g = take n
\x -> map (subtract 1) (take n x)

This works: take n x is a list and map takes a list.

Your third attempt:

map (subtract 1) . take n l
-- inline the definition of (.)
--   with f = map (subtract 1)
--   and g = take n l
\x -> map (subtract 1) (take n l x)

This fails because take n l x is a type error. It tries to apply take n l to x, which would require take n l to be a function, but it is a list.

In summary, . composes two functions of a single argument each. map foo . take fails because take is a function of two arguments; map foo . take n l fails because take n l is not a function at all (it takes zero arguments). In the working version, map foo . take n, we partially apply take and take n is indeed a function of one argument.

In order to compose a function of one argument with a function of two arguments, we could define another operator:

f .: g = \x y -> f (g x y)

Then we could write:

dec_first = map (subtract 1) .: take

Alternatively, we could write:

dec_first = (map (subtract 1) .) . take
-- which is the same as
dec_first = (.) (map (subtract 1)) . take

The reason this works is that the first . waits for one argument and passes it to take, then passes the result of that (a partially applied take x) to another ., which results in the map (subtract 1) . take x code that we already know works:

-- inline the first (.)
--   with f = (.) (map (subtract 1))
--   and g = take
dec_first = \x -> (.) (map (subtract 1)) (take x)
-- write (.) in infix notation
dec_first = \x -> map (subtract 1) . take x

We could even write our .: operator as a composition of compositions:

(.:) = (.) . (.)
-- inline the first layer of (.)
(.:) = \x -> (.) ((.) x)
-- eta-expand
(.:) = \x y -> (.) ((.) x) y
-- convert to infix notation
(.:) = \x y -> ((.) x) . y
-- inline the second layer of (.)
(.:) = \x y z -> (.) x (y z)
-- convert to infix notation
(.:) = \x y z -> x . y z
-- inline the third layer of (.)
(.:) = \x y z w -> x (y z w)
-- rename parameters
(.:) = \f g x y -> f (g x y)

posted 10 months ago

CC BY-SA 4.0

mauke‭

41 reputation 0 1 4 0

The quick fix is:

map (subtract 1) . take n $ l

When I put your function in my own Haskell compiler, I get:

Possible cause: ‘take’ is applied to too many arguments

Remember that in Haskell, we don't have functions with multiple parameters. We have functions with a single parameter, that return either values or new functions. (That, in turn, only take a single parameter).

map (subtract 1) . take n l is read by Haskell as (map (subtract 1)) . (take n l) .

• The first part is a function that maps a list of numbers to a list of numbers. It has type (Num b) => [b] -> [b].
• The second part is a function that maps an integer to a function that takes a list and returns a list. It has type Int -> [a] -> [a].

So it tries to do function composition, where the first function is of type ([b] -> [b]), and the second of type (Int -> [a] -> [a]). That's not compatible.

We can make it work by writing it as (map (subtract 1)) . take n)( l ), or the shorthand function map (subtract 1)) . take n $ l. Now we have a function that subtracts 1 from every element in a list, and takes the first n elements of the result. This function then gets our list as argument.

In your comment, you pointed out that you also tried:

dec_first = map (subtract 1) . take

This gave you a different error message:

Probable cause: `take' is applied to too few arguments

This time, we have the opposite situation. The function map (subtract 1) is a neat function that takes a list of Num and returns a list of Num: it is of type (Num a) => [a] -> [a].

You then try to apply this to take, whose type is Int -> [a] -> [a]. It's a function that takes an integer, to yield a function that takes a list and yields a list. But... Haskell doesn't see any integers!

We can fix this by giving it the Integer it wants:

dec_first n = map (subtract 1) . take n

If you're using GHCi, you can put :t in front of a function to see its type. For example:

ghci> :t map (subtract 1)
map (subtract 1) :: Num b => [b] -> [b]

This can be very helpful to see if the type of your function is what you expected it to be, and to see if it matches the functions you're feeding it.

posted 10 months ago

CC BY-SA 4.0

10mo ago

FractionalRadix‭

379 reputation 6 7 48 19