Could you please define the following functions in a haskell by using a bag modu

Question

Could you please define the following functions in a haskell by using a bag module:

1)listToBag takes a list of elements and returns a bag containing exactly those elements. The number of occurrences of an element in the list and in the resulting bag is the same.

2)bagToList takes a bag and returns a list containing exactly the elements occurring in the bag. The number of occurrences of an element in the bag and in the resulting list is the same.

3)insertElem takes an element and a bag and returns the bag with the element inserted. Bag insertion either adds a single occurrence of a new element to the bag or increases the number of occurrences of an existing element by one.

4)deleteElem takes an element and a bag and returns the bag with the element deleted. Bag deletion removes a single occurrence of an element from the bag, decreases the number of occurrences of an existing element by one, or does not change the bag if the element does not occur.

Explanation / Answer

Ordering words by frequency involves a little manipulation of the list of word groups. Each word group is a list of one or more instances of a single word. An easy way to order by frequency is to convert these lists into a pair of values, where the first element is the word count (frequency) and the second element is the word itself. A simple function can perform this action on a single list of words:

makePair l = (length l, head l)
Converting a list of word groups is as simple as using map to apply this function over the entire list:

-- convert [["a", "a"], ["b"], ...]
-- into [(2, "a"), (1, "b"), ...]
map makePair wordGroups
However, makePair is deeply tied to the problem we are trying to solve and isn't very generic. Instead of creating a name for this throwaway function, we can use a lambda expression to define this function in-place:

-- same as above
map (l -> (length l, head l)) wordGroups
The character starts a lambda, or an anonymous function. Named parameters are found to the left of the arrow and the body of the function is found to the right of the arrow.

Generating the list of words and their frequencies is only part of the solution. Next, the words need to be sorted in descending order:

reverse (sort (map (l -> (length l, head l)) wordGroups))
Unfortunately, the nesting parentheses complicate the structure of this expression. We can use the $ operator to clean up the expression like so:

reverse $ sort $ map (l -> (length l, head l)) wordGroups
The $ operator is a little bit of syntactic sugar. It takes everything to the right and treats it as a single expression, then uses the right hand side as the last parameter to the expression on the left hand side. Therefore, these two forms are actually seen by the compiler as the very same expression.

The updated top10 function now looks like this:

top10 doc = ....
where
listOfWords = words (lowercase doc)
wordGroups = group (sort listOfWords)
frequencies = reverse
$ sort
$ map (l -> (length l, head l))
wordGroups
...
Next, the list of (frequency, word) pairs need to be reduced to a list of words. Pairs are such a useful data structure in Haskell programs that the Prelude includes two functions to get at their contents: fst returns the first element in a pair, and snd returns the second element in a pair. To get the words out of these pairs, we need to use snd. To convert the list of pairs into a list of words, we just need to use map:

top10 doc = ....
where
listOfWords = words (lowercase doc)
wordGroups = group (sort listOfWords)
wordPairs = reverse
$ sort
$ map (l -> (length l, head l))
wordGroups
wordsByFreq = map snd wordPairs
Finally, the goal of the top10 function is to find the ten most frequent words in a document. Since wordsByFreq is ordered from most frequent to least frequent, all we need to do is find the first ten elements in the list. This behavior is captured in the take function in the Prelude. take has two parameters: a desired size and a list of values; it returns a list no larger than the desired size.

With this one last piece of the puzzle, here is the complete definition of the top10 function:

import Data.Char
import Data.List

lowercase = map toLower

top10 doc = take 10 wordsByFreq
where
listOfWords = words (lowercase doc)
wordGroups = group (sort listOfWords)
wordPairs = reverse
$ sort
$ map (l -> (length l, head l))
wordGroups
wordsByFreq = map snd wordPairs
Loading the full text of RFC 822 into a value named rfc822, and running that string through top10 produces this result:

Loading package base ... linking ... done.
[1 of 1] Compiling Main ( top10.hs, interpreted )
Ok, modules loaded: Main.

*Main> rfc822 <- readFile "rfc0822.txt"
*Main> top10 rfc822
["the","of","to","a","is","and","be",";","for","in"]
*Main>
Using this bottom-up approach to defining a function like top10, we could write a series of similar functions. For example, a version that strips leading and trailing punctuation characters on each word. Or a version that builds a unique list of words, for use inside a spell checker. Or a version that returns both words and frequencies. Or a version that ignores stopwords like the, of and to in the source text. Writing a series of these functions will likely identify common components, like a function that converts a list of words to a list of (frequency, word) pairs, or a function that converts a list of pairs into a list of words.

The list goes on, and I encourage you to play with this simple little function to explore Haskell further.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.