Haskell: Replacing element with a given key in an association list

Question

I've got to make a function which is given a key (as a String), a value (as a String) and an association list of keys and values (as [(String, String)]). The function is meant to add the key/value pair on to the end of the list, and, if the key is already present in the list with an associated value, delete the old value.

I've tried using lookup on the key and association list, but I'm not sure what to do with the output - the output type of the lookup function is Maybe String, and I can't seem to do list functions (like dropping elements) on it. Is there any way I can look through the list and delete any list element with a given key without knowing the value associated with it?

Answer 1

In Haskell, we often use the Maybe datatype when we're not sure whether we'll get a value or nothing at all as a result. It's equivalent to a nullable type in a more traditional language such as Java.

Maybe is defined as follows:

data Maybe a = Nothing | Just a

That is, the value can either be Nothing or Just a, where a is the object you were looking for. For example, if you were searching for the string "foo" using the lookup function, and you had a ("foo", "bar") tuple inside your list, you'd get the result Just "bar". However, if you looked up "xyzzy", you'd get Nothing.

We can take the Maybe value and turn it into something more useful using the maybe function (confusing names, I know - the function is all lowercase). It's defined as follows:

maybe default f (Just a) = f a
maybe default f Nothing  = default

The first parameter is a default value. This is what we get back if we have Nothing. Otherwise, we get the function f applied to a, where a is the thing we want. If you just want a back, you can pass the id function as f:

maybe default id (Just a) = id a

Helpfully, id a = a.

If you want to continue using your current lookup plan, this is how you'll get something useful out of it. I personally favour sth's method though - it'd be easier on the processor.

Answer 2

Here's a simple function that does what you want. It takes the new key value pair and puts that at the front of the given assoc list with that key filtered out.

addOrReplace :: Eq k => k -> v -> [(k, v)] -> [(k, v)]
addOrReplace key value assoc = (key,value):(filter ((key /=).fst) assoc)

The function fst is defined as:

fst (first,second) = first

filter takes a predicate and a list, and returns the list with only those elements that satisfy the predicate.

Edit: Split the key value pair in the parameters for addOrReplace as Tom suggests.

Answer 3

You should probably write a recursive function that takes the new key/value-pair and the existing list as parameters, and loops through the list to generate a new list with the new value inserted. For each list element you check if the key is the same as the one you want to insert. If it's different you keep that old element, if it's the same you add the new item instead of the old one. If you reach the end of the list without finding the key you just insert the new item there at the end.