Functionality of adding to lists in Haskell / overwriting an existing List

Question

type Dictionary = [(String, String)]

dict :: Dictionary
dict = ("Deutsch", "English"):[]

insert :: Dictionary -> (String,String) -> Dictionary
insert dict entry = dict ++ [entry]

One thing that I didn't find about the way lists work: Is it somehow possible to overwrite the existing dict with the entry added in insert? Or is it necessary to, in the next step, always write out the list that was put out by insert?

insert [("German", "English"), ("Hallo", "hello")] ("Versuch", "try")

So far, this is the only way I have been able to add something to the new list without losing the previous entry. However, next on the list of things to implement is a search command, so I wonder if I'd also have to write this out in the search function.

What exactly do you mean by "write this out"? By the way, the rigt hand side of your insert function would be better simply `entry:dict` — Ingo, Dec 13 '13 at 13:21
If you're creating an association list, if you insert at the front of the list then you don't need to remove the previous value since any search will find the item added most recently. — Lee, Dec 13 '13 at 13:21
I already tried using the cons operator, but it seems like my list, as it stands, is no association list? Because I encounter the same problem when I change the operator from ++ to :, all I ever got was one additional entry without renaming everything like in RasmusWriedtLarsen's example. @Ingo What I meant was NOT giving the new lists names with let dict2 an so on, but rather write the entire list with its entries like in the insert command I wrote in my question. — dschib, Dec 13 '13 at 13:43

RasmusWL · Accepted Answer · 2013-12-13T14:06:22.263

2

The idea of functional programming is in general that your data is immutable. This means once you have created a list, you can NEVER change that list. But you can copy that list, make modifications to it, and keep that as well.

So when you have a list like so

test = [1,2,3]

We can modify this by adding 4 to the start:

test2 = 4 : test

: called the cons operator, puts an element in front of a list. Do note that x:xs (the same as doing [x]++xs) has a better performance than doing xs++[x]

So now we have two bindings, one of test to [1,2,3] and one of test2 to [4,1,2,3]

Hope this clarifies things

To give a full example:

type Dictionary = [(String, String)]

insert :: Dictionary -> (String,String) -> Dictionary
insert dict entry = dict ++ [entry]

dict0 = [ ("Deutsch", "English") ]
dict1 = insert dict0 ("Hallo", "hello")
dict2 = insert dict1 ("Versuch", "try")

If you're new to functional programming, I would recommend reading Learn You a Haskell for Great Good , which is a fantastic (and free) book on how to use Haskell -- and functional programming in general.

edited Dec 13 '13 at 14:06

answered Dec 13 '13 at 13:24

RasmusWL

1,573
13
26

If I try to do this in the command line, I would have to add let first, right? like `let dict1 = insert dict0 ("Hallo", "Hello")`? – dschib Dec 13 '13 at 13:38
dict ++ [entry] -- adding one element to the end of list is very bad in terms of performance. Why don't just use the colon operator? – user3974391 Dec 13 '13 at 13:41
I thought it would be clever to have the headline ("Deutsch", "English") at the head of the list, and if I add to the beginning of the list, the head would constantly change, wouldn't it? @user2894391 – dschib Dec 13 '13 at 13:44
@dschib Changing of head is the cheapest list operation so it is preferable then possible. – user3974391 Dec 13 '13 at 13:49
Wouldn't I have to do this permanently once I prepend a new element with `:`? Or is there a way to let the head stick? – dschib Dec 13 '13 at 13:56
If doing something like this, you would probably not add the name of the languages to the lists, as it's implicit. It kinda breaks the information contained in the the list, where you have a tuple of a word in (Deutsch, English) ... but ("Deutsch", "English") is certainly not the same thing in two different languages. – RasmusWL Dec 13 '13 at 14:05
So I'll just leave it out and add the words, well, then prepending should indeed be no problem. Thanks for all the help! – dschib Dec 13 '13 at 14:08
The only problem being that let is exclusive to GHCi, while I'm stuck with hugs at the moment. – dschib Dec 13 '13 at 14:42

Chris Taylor · Answer 2 · 2013-12-13T13:54:20.937

1

It's not too tough to do this

import Data.List (lookup)

insert :: Eq a => (a,b) -> [(a,b)] -> [(a,b)]
insert (a,b)  []           = [(a,b)]
insert (a,b) ((c,d):rest) = if a == c
    then (a,b) : rest
    else (c,d) : insert (a,b) rest

---

dict :: [(String, String)]
dict = [("Deutsch", "English")]

If you can't use Data.List then you can define lookup by

lookup :: Eq a => a -> [(a,b)] -> Maybe b
lookup _  []          = Nothing
lookup k ((a,b):rest) = if k == a then Just b else lookup k rest

Now if you load up GHCI:

>> let dict' = insert ("Ein","One") dict
>> dict'
[("Deutsch","English"),("Ein","One")]
>> lookup "Ein" dict'
Just "One"
>> insert ("Deutsch", "Francais") dict'
[("Deutsch","Francais"),("Ein","One")]

edited Dec 13 '13 at 13:54

answered Dec 13 '13 at 13:23

Chris Taylor

46,912
15
110
154

The thing about this task is to not do it with Data.List since we aren't that far right now and still have to grasp the basics of functional programming. – dschib Dec 13 '13 at 13:35
@dschib I edited to remove the dependency on `Data.List` – Chris Taylor Dec 13 '13 at 13:39
Thanks a lot, the lookup function will help me out greatly! – dschib Dec 13 '13 at 13:51

score 0 · Answer 3 · answered Dec 13 '13 at 13:24

If you want to replace an existing pair with the same key then you could write insert as:

insert :: Dictionary -> (String, String) -> Dictionary
insert [] p = [p]
insert ((dk, dv):ps) p@(k, v) | dk == k = p:ps
insert (p:ps) ip = p : (insert ps ip)

However if you are writing an association list, then you can simplify it by inserting new items at the front of the list:

insert :: Dictionary -> (String, String) -> Dictionary
insert = flip (:)

if you then search from the front of the list, it will find any values added more recently first.

score 0 · Answer 4 · answered Dec 13 '13 at 13:25

0

In Haskell, most values are immutable, meaning that you can not change their value. This seems like a huge constraint at first, but in reality it makes it easier to reason about your program, especially when using multiple threads.

What you can do instead is continually call insert on the dictionary returned when you call insert, for example:

mainLoop :: Dictionary -> IO ()
mainLoop dict = do
    putStrLn "Enter the German word:"
    german <- getLine
    putStrLn "Enter the English word:
    english <- getLine
    let newDict = insert dict (german, english)
    putStrLn "Continue? (y/n)"
    yesno <- getChar
    if yesno == 'y'
        then mainLoop newDict
        else print newDict

main = do

answered Dec 13 '13 at 13:25

bheklilr

53,530
6
107
163

I would love to work with IO, however that is far from where we are in our lecture right now. All we should do is use the insert command in the command line, without prompts or anything of the sort. The main problem I had with understanding this is if there is anyway to have dict NOT be immutable, but I guess that is like trying to throw pearls before the swine. – dschib Dec 13 '13 at 13:31
Not without IO. You could use the State monad, but if IO is beyond your current lectures, that is too. Right now you'll just have to keep rebinding it as @RasmusWriedtLarsen suggests. – bheklilr Dec 13 '13 at 14:06

score 0 · Answer 5 · answered Dec 13 '13 at 13:34

0

One simply can't 'overwrite' anything in a pure language (outside of ST monad). If I understood your question correctly, you are looking for something like this:

insert :: Dictionary -> (String,String) -> Dictionary
insert [] b = [b]  -- If this point is reached where wasn't matching key in dictionary, so we just insert a new pair
insert (h@(k, v) : t) b@(k', v')
    | k == k'   = (k, v') : t      -- We found a matching pair, so we 'update' its value
    | otherwise = h : insert t b

answered Dec 13 '13 at 13:34

user3974391

701
4
14

The check for duplicates is not necessary in my task, the main problem I had with my understanding is seein how every dict I define is immutable as it is, so if I want to have a new name for a dict that has more than one entry I would have to use `let dict3 = insert dict2 ("This", "that")`. – dschib Dec 13 '13 at 13:49
@dschib You may use state monad to simulate variables. – user3974391 Dec 13 '13 at 13:52
Again, something I can look up in the future, the last thing we had in our lecture were arrays, and monads are a long way down the road... – dschib Dec 13 '13 at 13:57

Functionality of adding to lists in Haskell / overwriting an existing List

5 Answers5

Linked