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

Question

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.

Certainly it's possible with a fold, and may be a useful learning exercise. But once you've learned how to write this as a fold, instead write it in this simpler way: `(!!=) xs (i, a) = case splitAt i xs of { (pref, (_:post)) -> pref ++ [a] ++ post }` (where `splitAt` comes from Data.List) — user2407038, Apr 16 '21 at 17:29
Thanks a lot I didn't consider using splitAt before this is very helpful — andreadhelpra, Apr 16 '21 at 18:11

score 2 · Accepted Answer · answered Apr 16 '21 at 17:18

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

dfeuer · Answer 2 · 2021-04-19T01:39:01.140

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.

I know we had this conversation before, but I still don't understand and don't remember now why one should be a "classic trick", and the other, "cheating". Even if it fuses badly, say, it's still not "cheating"? A right fold with a left-to-right state passing is always going to need the extra argument (or two) to pass the state in, and whether I update that state with a `(+1)` or an unconditional (and correct by construction) `tail`, what's the diff really? So using this to emulate a paramorphism should be fine, but if not, there's always `tails` to fold over. now _that_ cld be "cheating". :) — Will Ness, Apr 25 '21 at 06:48
@WillNess, I'm often opinionated. I remember this cheat being used for one library function somewhere—don't remember what. I'm not the biggest fan of pattern matching twice on the same thing in general, though I did it in [`Data.Biapplicative.traverseBia`](https://hackage.haskell.org/package/bifunctors-5.5.7/docs/Data-Biapplicative.html#v:traverseBia) to avoid `unsafeCoerce`. — dfeuer, Apr 25 '21 at 18:19
OK, that's something. thanks! :) BTW if you remember, in the less scrupulous Common Lisp they do have this thing called `maplist` which _is_ `map` on `tails` (and the regular `map` they call `mapcar`). — Will Ness, Apr 25 '21 at 18:25
@WillNess, my only exposure to CL was looking at a manual one time. It was a bit traumatizing. — dfeuer, Apr 25 '21 at 18:26
I can relate. :) But I meant maybe you remembered it from that previous convo, where I also mentioned that [pretend-paramorphism](https://stackoverflow.com/a/25853459/849891) that uses that technique (I think I did). — Will Ness, Apr 25 '21 at 18:28

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

2 Answers2