I need to implement a function that replaces elements in a list -- the
index to replace at is the fst in the tuple, and the snd in the tuple
is what to replace it with. and I am asked to use foldr or map function.
for example:
setElements [(1, 'a'), (-4, 't'), (3, 'b')] "#####" = "#a#b#"
the setElements function doesn't compile:
my code:
setElement :: Int -> a -> [a] -> [a]
setElement n x xs = if ((n < length xs) && n >= 0)
then (take n xs) ++ [x] ++ (drop (n + 1) xs)
else xs
setElements :: [(Int, a)] -> [a] -> [a]
setElements = foldr (\t l-> setElement (fst t) (snd t) l) []
I get:
• Couldn't match type ‘[a]’ with ‘[a] -> [a]’
Expected type: [(Int, a)] -> [a] -> [a]
Actual type: [(Int, a)] -> [a]
• Possible cause: ‘foldr’ is applied to too many arguments
In the expression: foldr (\ t l -> setElement (fst t) (snd t) l) []
In an equation for ‘setElements’:
setElements = foldr (\ t l -> setElement (fst t) (snd t) l) []
• Relevant bindings include
setElements :: [(Int, a)] -> [a] -> [a]
(bound at hw3.hs:79:1)
|
79 | setElements = foldr (\t l-> setElement (fst t) (snd t) l) []
|
How can I fix the error?
Let's look at your function:
setElements :: [(Int, a)] -> [a] -> [a]
setElements = foldr (\t l-> setElement (fst t) (snd t) l) []
and recall the type of foldr:
foldr :: (a -> b -> b) -> b -> [a] -> b
In your use of foldr, you have a as (Int, a) and b as [a]. And you only give it the first 2 arguments. So foldr (\t l-> setElement (fst t) (snd t) l) [] has type [(Int, a)] -> [a] - whereas setElements is supposed to have type [(Int, a)] -> [a] -> [a]. Note how these match exactly with the "actual type" and "expected type" reported by GHC in the error message.
To fix this, I would actually take a step backwards. Folding is the right idea - your setElement function already modifies the original list (its third argument) based on an index and new value, and what you want is to take a list of pairs encoding this data, and keep on applying this function to update the original list repeatedly. (Of course this is Haskell so data is immutable - you're not literally updating it in place, but simply returning a new list each time. But sometimes talking loosely like this is easier.)
That's exactly what a fold is. Let's try to write it out, without trying to be too fancy with a "point-free" approach, but instead fully applying it:
setElements :: [(Int, a)] -> [a] -> [a]
setElements ps as = foldr myFunction as ps
where myFunction = undefined
The undefined here is just a placeholder - it will cause a runtime error if you try to use the function (but won't cause a compilation error), and I've put it there because we need to think about that, the fold function usually being the trickiest part of implementing a fold. But let's check we understand what the other terms are doing: the list we are actually "walking along" is the list of (Int, a) terms that tell us what to insert and where - that's what I've called ps (the p is for "pair"). And because we are starting with the list of as - which I've logically called as here - then that should be the starting accumulator value, which is the second argument to foldr.
So all that remains is the fold function - which takes a pair and a list, and updates the list according to the values in the pair. Well this is the function you're already using:
\t l-> setElement (fst t) (snd t) l
or, rewritten with pattern matching (which I find much more readable, and for this reason I think is preferred by most Haskell developers):
\(i, a) as -> setElement i a as
So, substituting this in, we arrive at the following definition:
setElements :: [(Int, a)] -> [a] -> [a]
setElements ps as = foldr myFunction as ps
where myFunction = \(i, a) as -> setElement i a as
This now will compile and work correctly. But it's always worth taking a step back when you have a working function, and seeing if you can simplify its definition. In fact myFunction can be simplified quite a bit:
\(i, a) as -> setElement i a as
can first be "eta-reduced" to
\(i, a) -> setElement i a
which, using a standard library function, is simply uncurry setElement.
At this stage we clearly don't need a where clause any more (in fact we never did before, but imo it aids readability for any lambda which isn't fairly trivial), and can just write:
setElements :: [(Int, a)] -> [a] -> [a]
setElements ps as = foldr (uncurry setElement) as ps
In fact, while I wouldn't necessarily recommend it, if we're playing code golf you can even go a step further and just write:
setElements = flip . foldr . uncurry $ setElement
I personally think the ability to be able to express relatively complex functions in a concise way, as above, is definitely part of the allure of Haskell. But, rather than try to write something like this straight away, in my opinion it's always best to start with something very concrete showing how you want to transform your data - and, only after getting that working, look for a more concise representation if you want to.