Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Welcome to Software Development on Codidact!

Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.

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

Parent

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

+6
−0

Can anyone explain to me why my Haskell function gives rise to a type-definition error?

Originally, I wrote the following function to subtract one from the first n elements in a list:

dec_first :: Int -> [Int] -> [Int]
dec_first 0 l = l
dec_first n (x:xs) = (x-1):dec_first (n-1) xs

However, as a challenge, I wanted to write this function using available standard functions, using function compositions. This is how I ended up writing the function (for the subtraction part)

dec_first :: Int -> [Int] -> [Int]
dec_first = map (subtract 1) . take

but this function does not compile due to a type mismatch.

In my attempt to fix the error, I also tried the following variant:

dec_first :: Int -> [Int] -> [Int]
dec_first n = map (subtract 1) . take n

This function actually does work as expected. However, if I specify all parameters again, things breaks again:

dec_first :: Int -> [Int] -> [Int]
dec_first n l = map (subtract 1) . take n l

Can anyone help me understand why this function only works with one variable, but not in the other settings?

History
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

Post
+4
−0

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)
History
Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment thread

Works for me (1 comment)
Works for me
mr Tsjolder‭ wrote 10 months ago

the insight on the signature of the composition operator explains my misunderstanding very well!