High order function thats has for input a list of functions and a list of elements and applies the functions to the elements

Question

As the title suggests i am trying to implement a high order function declared as

Ord u => [v->u]->[v]->[u]

that has inputs a) a list of functions of any type and a range of values of any type and b) a list of elements of the same type and then it will return a list that is the result of all elements that occured from applying a function from the given list to an element from the given list in ascending order without repetitive values.

i was trying to implement it with the foldr function with no luck. i thought that i can index with zip the functions as a pair so they will be applied one by one with the foldr function. bellow that i created a insertion sort so i can sort the final list

apply :: Ord u => [v->u]->[v]->[u]             
apply f y = insSort (foldr(\(i, x) y -> x:y ) (zip [1..] f))

insSort :: Ord u => [u] -> [u]
insSort (h:t) = insert h (insSort t)
insSort [] = []

insert :: Ord u => u -> [u] -> [u]
insert n (h:t)
            | n <= h = n : h : t
            | otherwise = h : insert n t
insert n [] = [n]

for example some inputs with the output:

>apply [abs] [-1]
[1]

>apply [(^2)] [1..5]
[1,4,9,16,25]

>apply [(^0),(0^),(\x->div x x),(\x->mod x x)] [1..1000]
[0,1]

>apply [head.tail,last.init] ["abc","aaaa","cbbc","cbbca"]
"abc"

> apply [(^2),(^3),(^4),(2^)] [10]
[100,1000,1024,10000]

>apply [(*5)] (apply [(‘div‘5)] [1..100])
[0,5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100]

Benjamin Hodgson Benjamin Hodgson · Accepted Answer · 2017-03-27T20:24:03

apply :: [a -> b] -> [a] -> [b]

First of all, this signature matches that of the standard <*> function, which is part of the Applicative class.

class Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

Setting f ~ [] we have <*> :: [a -> b] -> [a] -> [b].

There are at least two sensible ways of writing an Applicative instance for lists. The first one takes the Cartesian product of its inputs, pairing every function with every value. If <*>'s input lists have length N and M, the output list will have length N*M. pure for this specification would put an element in a singleton list, so that pure id <*> xs = xs.

instance Applicative [] where
    pure x = [x]
    (f:fs) <*> xs = map f xs ++ (fs <*> xs)

This is equivalent to the standard Applicative instance for [].

The other sensible way of implementing Applicative zips the two lists together by applying functions to elements pointwise. If <*>'s input lists have length N and M, the output list will have length min(N, M). pure creates an infinite list, so once again pure id <*> xs = xs.

instance Applicative [] where
    pure x = let xs = x:xs in xs
    [] <*> _ = []
    _ <*> [] = []
    (f:fs) <*> (x:xs) = f x : (fs <*> xs)

This instance is available in base under the ZipList newtype.

High order function thats has for input a list of functions and a list of elements and applies the functions to the elements

1 Answers