Currently, I am working on trying to take a list of integers (Int), and put them into a multiset representation. For a little background, the representation would look like this:
*user passes in a list:* [1,2,3,4]
*multiset representation:* [(1,1),(2,1),(3,1),(4,1)]
I have written two functions: add and del. add takes an integer and a bag, and inserts the integer into the bag. It checks for duplicates - if there are, it simply increments the counter (second element of coordinate in bag) by 1. It then returns that bag.
So, my algorithm should be: take the list, say [1,2,3,4]; go through each element in the list - and for each of these elements, call add with the parameters being the current element and the bag. For the next element, do the same - pass the element, with the bag that was returned from the previous add call.
Here's what I'm shaky on: how would I actually code this? I've put my (not so good) attempt down below. I've figured out the algorithm completely, but am unsure of how to execute this. Any tips in the right direction would be great.
multi :: Eq a => [a] -> Bag a
multi [] = []
multi (x:xs) = ins x []
As you said, you've figured out the algorithm; you can translate it almost directly into Haskell:
-- So, my algorithm should be: take the list, say [1,2,3,4];
multi :: Eq a => [a] -> Bag a
-- go through each element in the list
multi [] = []
multi (x:xs) =
-- and for each of these elements, call add with the parameters being the current element
-- and the bag.
let returnedBag = add x theBag
-- For the next element, do the same - pass the element, with the bag that was returned
-- from the previous add call.
in doTheSame xs returnedBag
Of course, this doesn't quite work, because two definitions are missing: what is doTheSame, and what is theBag? Well, we'd want doTheSame to mean everything in the body of multi right now, but notice that we want to pass two arguments to doTheSame instead of the one that multi takes. So let's try making doTheSame its own function:
-- So, my algorithm should be: take the list, say [1,2,3,4];
multi :: Eq a => [a] -> Bag a
-- go through each element in the list
multi elts = doTheSame elts ???
where
doTheSame [] theBag = ???
doTheSame (x:xs) theBag =
-- and for each of these elements, call add with the parameters being the current element
-- and the bag.
let returnedBag = add x theBag
-- For the next element, do the same - pass the element, with the bag that was returned
-- from the previous add call.
in doTheSame xs returnedBag
This solves what theBag is—it's just whatever's passed to doTheSame. But now we have some ??? placeholders in there which need to be filled with something. What should multi do when it's done processing elements? Return the bag it has been building, no doubt:
-- So, my algorithm should be: take the list, say [1,2,3,4];
multi :: Eq a => [a] -> Bag a
-- go through each element in the list
multi elts = doTheSame elts ???
where
doTheSame [] theBag = theBag
doTheSame (x:xs) theBag =
-- and for each of these elements, call add with the parameters being the current element
-- and the bag.
let returnedBag = add x theBag
-- For the next element, do the same - pass the element, with the bag that was returned
-- from the previous add call.
in doTheSame xs returnedBag
And what about the ??? first given to doTheSame? That must be the bag that you start with—presumably, an empty bag. (You'll need to define what that is for yourself.)
-- So, my algorithm should be: take the list, say [1,2,3,4];
multi :: Eq a => [a] -> Bag a
-- go through each element in the list
multi elts = doTheSame elts emptyBag
where
doTheSame [] theBag = theBag
doTheSame (x:xs) theBag =
-- and for each of these elements, call add with the parameters being the current element
-- and the bag.
let returnedBag = add x theBag
-- For the next element, do the same - pass the element, with the bag that was returned
-- from the previous add call.
in doTheSame xs returnedBag
This code works, assuming you have a definition of add and emptyBag! But you might want to tidy it up a little. A more experienced Haskell programmer would probably use some shorter names, and bring returnedBag inline:
-- So, my algorithm should be: take the list, say [1,2,3,4]; go through each element in the
-- list - and for each of these elements, call add with the parameters being the current
-- element and the bag. For the next element, do the same - pass the element, with the bag
-- that was returned from the previous add call.
multi :: Eq a => [a] -> Bag a
multi elts = go elts emptyBag
where go [] bag = bag
go (x:xs) bag = go xs (add x bag)
This code is exactly the same as the previous—the only reason to prefer one over the other is whether you find one easier to read. (Never underestimate the importance of being able to read your own code, and never overestimate your ability to do so after some time has passed and it's no longer fresh in your mind!)
Extra credit:
This kind of recursion is very common in functional languages in general, and is typically called a fold. A fold starts with some data (in this case, an empty bag), walks over a list or list-like structure, and for each element in that structure, uses a function (in this case, add) to combine the data with the element to make new data, which is used on the next element, and so on, returning the final value of the data (in this case, a bag with all your elements). Since this is a common pattern, in Haskell, there is a function called foldl (for left fold, since you're processing your list elements starting from the left) that takes just a combining function, an initial value, and a list, and does all the rest of the work for you:
multi :: Eq a => [a] -> Bag a
multi elts = foldl (\bag x -> add x bag) emptyBag elts
While you're still learning about recursion and the basics of Haskell, I wouldn't try too hard to write code in the style of that last version of multi. But once you've done the where go trick a few times and have gotten sick of writing all that out every time, go look up foldl and foldr and take the next step!