CODEWITHSUNDEEP
listhaskellfunctional-programmingpattern-matchingfold
andreadhelpra
andreadhelpra

Reputation: 27

Haskell - using foldl or foldr instead of pattern matching for updating a list with a new value at a given index

I have implemented a function (!!=) that given a list and a tuple containing an index in the list and a new value, updates the given list with the new value at the given index.

(!!=) :: [a] -> (Int,a) -> [a]
(!!=) xs (0, a) = a : tail xs
(!!=) [] (i, a) = error "Index not in the list"
(!!=) (x:xs) (i, a) = x : xs !!= (i-1, a)

Being a beginner with the concept of folding I was wondering if there is a way to achieve the same result using foldl or foldr instead?

Thanks a lot in advance.

Upvotes: 0

Views: 871

Answers (2)

dfeuer
dfeuer

Reputation: 48591

Neither foldl nor foldr can do this particular job efficiently (unless you "cheat" by pattern matching on the list as you fold over it), though foldr can do it a bit less badly. No, what you really need is a different style of fold, sometimes called para:

para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para _f n [] = n
para f n (a : as) = f a as (para f n as)

para is very similar to foldr. Each of them takes a combining function and, for each element, passes the combining function that element and the result of folding up the rest of the list. But para adds something extra: it also passes in the rest of the list! So there's no need to reconstruct the tail of the list once you've reached the replacement point.

But ... how do you count from the beginning with foldr or para? That brings in a classic trick, sometimes called a "higher-order fold". Instead of para go stop xs producing a list, it's going to produce a function that takes the insertion position as an argument.

(!!=) :: [a] -> (Int, a) -> [a]
xs0 !!= (i0, new) = para go stop xs0 i0
  where
    -- If the list is empty, then no matter what index
    -- you seek, it's not there.
    stop = \_ -> error "Index not in the list"

    -- We produce a function that takes an index. If the
    -- index is 0, we combine the new element with "the rest of the list".
    -- Otherwise we apply the function we get from folding up the rest of
    -- the list to the predecessor of the index, and tack on the current
    -- element.
    go x xs r = \i -> case i of
      0 -> new : xs
      _ -> x : r (i - 1)

Note that para is easily powerful enough to implement foldr:

foldr c = para (\a _ b -> c a b)

What's perhaps less obvious is that foldr can implement a (very inefficient version of) para:

para f n = snd . foldr go ([], n)
  where
    go x ~(xs, r) = (x : xs, f x xs r)

Lest you get the wrong idea and think that para is "better than" foldr, know that when its extra power isn't needed, foldr is simpler to use and will very often be compiled to more efficient code.

Upvotes: 0

Random Dev
Random Dev

Reputation: 52280

I'll give you the foldl version which is easier to understand I think and the easiest / most straight-forward version I can think of.

But please note that you should not use foldl (use foldl': https://wiki.haskell.org/Foldr_Foldl_Foldl') - nor should you use ++ like this (use : and reverse after) ;)

Anway this is the idea:

(!!=) xs (i, a) = snd $ foldl 
   (\(j, ys) x -> (j+1, if j == i then ys ++ [a] else ys ++ [x])) 
   (0, []) 
   xs
  • as the state/accumulator for the fold I take a tuple of the current index and the accumulated result list (therefore the snd because I only want this in the end)
  • then the folding function just have to look if we are at the index and exchange the element - returning the next index and the new accumulated list

as an exercise you can try to:

  • use : instead of ++ and a reverse
  • rewrite as foldr
  • look at zipWith and rewrite this using this (zipWith (...) [0..] xs) instead of the fold (this is similar to using a map with index

Upvotes: 2

Related Questions