How do you solve this Haskell problem using higher order functions?

Question

Using higher order functions (map, fold or filter) and if necessary lambda expressions. Write a definition for f1 and f2 so the following evaluation is valid:

f1 (f2 (*) [1,2,3,4]) 5 == [5,10,15,20]

Any help would be appreciated, thanks.

Answer 1

for you problem try doing this.

map (*5) ([1,2,3,4])

If you want to learn high order read what follows

map is function which applies another function to each element in a list. (Pardon my english) As you can see map is a function that receive another function (f in this case) and applies it to every element in the list.

map :: (a -> b) - [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

There are two other interesting high order functions, filter which removes the elements from a list according to a boolean function. And fold which is clearer with an example:

~> : means returns

foldr (+) 0 [1,2,3,4] ~> 10
foldr (*) 1 [1,2,3,4] ~> 24

so we can write foldr as this.

foldr :: (a -> a -> a) -> a -> [a] -> a
foldr f a [] = a
foldr f a (x:xs) = x ‘f‘ (foldr f a xs)

Answer 2

Is this a homework, by any chance? If so, then you may want to add the "homework" tag - people will still give you an answer, but they will try to point you in the right direction and explain the problem, rather than showing only code (sorry if that's not the case!)

Anyway, based on the input data, it seems that you need to multiply the elements of the given list by the number 5 given as the last argument to f1. You definitely won't need filter as this changes the length of the list.

You could start from the inner-most part f2 (*) [1,2,3,4]. You can use the map function here and as a result, you'll get a list of functions that multiply the numbers by a given argument. Something like [(\x -> x*1), (\x -> x*2), (\x -> x*3), ...].

Now you need to implement f1, such that:

f1 [(\x -> x*1), (\x -> x*2), (\x -> x*3), ...] 5 = [5, 10, 15, ...]

I don't think you can do this using any built-in function directly, so I would use a lambda expression in place of f1 - internally, you'll need to apply some operation to all elements of the list (given as the first parameter), which can be again done using map.

Answer 3

Here some things to think about:

• What is the type of (*)?

• What the type of the left and right sides of the equation?

• Given that f1 (...) is applied to 5 and produces a list of numbers, what is the type of this application?

• What are the types of the argument to f2?

• What result type for f2 makes the most sense to you, and why?

• Given that the only two lists involved in the problem have the same length, how likely is it that map is used?

• Given that the only two lists involved in the problem have the same length, how likely is it that filter is used?

• Given that the only two lists involved in the problem have the same length, how likely is it that fold is used?

Answer 4

f1 (f2 (*) [1,2,3,4]) 5 == [5,10,15,20]

What you know:

• f2 takes two arguments the multiplication function (*), and [1,2,3,4]
• f1 takes the result of f2, and 5 and must return [5,10,15,20] (assuming == is sane)

Notice, you want this effect.

[5,10,15,20] / 5 = [1,2,3,4]
[1,2,3,4] * 1 = [1,2,3,4]

See if that helps.

I'm just going to give you the solution for fun

f2 _ a = a
f1 a b = zipWith (*) a $ repeat b
f1 ( f2 (*) [1,2,3,4]) 5

or, simply

let f2 _ a = a; f1 a b = Data.List.zipWith (*) a $ repeat b in f1 ( f2 (*) [1,2,3,4]) 5

Answer 5

Read @Norman Ramsey's comments and understand them before continuing. Here some hints for you:

Prelude> let f1 = map (*) [1,2,3,4]
Prelude> :t f1
f1 :: [Integer -> Integer]

So, what does this mean? It means the type of f1 is an array of functions that take an Integer and return an Integer. The first is (1*), the second is (2*), etc.

Prelude> (head f1) 5
5
Prelude> (head $ tail f1) 5
10

Since the first element in the list is a function (1*), passing it 5 returns 1*5=5. The second element of the list is (2*) so when I take it from the list (head $ tail f1) and pass it 5 it returns the result 2*5=10.

Now obviously you can't process the results using head and tail. However, based on this you should be able to write a recursive function with a base case for [] and code to process an actual function, such as (1*) or (2*), and then recurse. Once you have the recursive function working, reduce it to an anonymous function suitable to pass to a "higher order function". This shouldn't be too bad. You can try the archives of Haskell beginners if you get stuck.

In short, writing the recursive version is often easier. Once that is done, throw out the boiler plate (the base case and the recursive call) and look at what is left. That is the useful bit of code you need to pass to the "higher order function".