CODEWITHSUNDEEP
haskellhigher-order-functionsfold
ddaakk
ddaakk

Reputation: 19

How can i fix this higher order function code in haskell?

I want to fix this code

h :: (a -> b) -> [a] -> [b]
h f = foldr (\x y -> f x : y) []

if i put h (+100) [1,2,3,4,5] in GHCI

it returns to me [101,202,303,404,505]

when i put h (*10) [1,2,3,4,5] then

i want to get [10,200,3000,40000,500000] list

can anyone help me fixing this code?

Upvotes: 1

Views: 101

Answers (2)

dfeuer
dfeuer

Reputation: 48601

Solving the general problem, as Willem Van Onsem's answer does, requires O(n^2) time to calculate the first n elements, because the function has to be applied k times to calculate the kth element.

To solve this sort of problem efficiently, you will need to take advantage of some additional structure. Based on your examples, I think the most obvious approach is to think about semigroup actions. That is, instead of applying an arbitrary function repeatedly, look for an efficient way to represent the compositions of the function. For example, (*x) can be represented by x, allowing (*x) . (*y) to be represented by x*y.

To apply this idea, we first need to transform Willem's solution to make the compositions explicit.

h :: (a -> a) -> [a] -> [a]
h f0 as0 = go as0 f0
  where
    go [] _ = []
    go (a:as) f = f a : go as (f0 . f)

If we like, we can write that as a fold:

h :: (a -> a) -> [a] -> [a]
h f0 as = foldr go stop as f0
  where
    stop _ = []
    go a r f = f a : r (f0 . f)

Now we've structured the function using an accumulator (which is a function). As we compose onto the accumulator, it will get slower and slower to apply it. We want to replace that accumulator with one we can "apply" quickly.

{-# language BangPatterns #-}
import Data.Semigroup

repeatedly :: Semigroup s => (s -> a -> a) -> s -> [a] -> [a]
repeatedly act s0 as = foldr go stop as s0
  where
    stop _ = []
    go a r !s = act s a : r (s0 <> s)

Now you can use, for example,

repeatedly (\(Product s) -> (s*)) (Product 10) [1..5]
==> [10,200,3000,40000,500000]

repeatedly (\(Sum s) -> (s+)) (Sum 100) [1..5]
==> [101,202,303,404,505]

In each of these, you accumulate a product/sum which is added to/multiplied by the current list element.

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476977

You here implemented a map, but in order to repeat the same operation multiple times, you need to perform a mapping on the tail y:

h :: (a -> a) -> [a] -> [a]
h f = foldr (\x y -> f x : map f y) []

Upvotes: 4

Related Questions