CODEWITHSUNDEEP
haskellfunctional-programming
Leon Cullens
Leon Cullens

Reputation: 12496

Haskell compare all list items

Edit: it's hard to describe what I'm trying to do, but here's a try (from the comments):

I am building a wordfeud solver, so I have a word, and some letters (both char list). I applied this ( How to find the frequency of characters in a string in Haskell? ) to both lists to get the frequency of all letters. What I'm doing now is iterating though the 'word' char list, and checking if all chars occur sufficiently in the 'letters' char list.

I have written a Haskell function that compares two lists by applying a function to the items of both lists, and comparing the results.

The comparison is done like this:

hasLetters' :: [Char] -> [Char] -> Bool
hasLetters' word letters = (getCharOccurrence (head word) (getCharOccurrences word)) <= (getCharOccurrence (head word) (getCharOccurrences letters))

This only compares the occurrences of the first letter of the word. But ALL words should be compared (and the result should be TRUE for all of them).

I don't really know how to accomplish this. I found the 'all' method that lets me define a predicate, that's pretty good. It looks like this:

all (<= (getCharOccurrence (head word) (getCharOccurrences letters)))

(I think that's correct) It makes sure that every item that goes into the list is smaller than or equal to the result of the provided function.

BUT: the 'all' method needs another parameter. This would be the 'source' parameter that defines what should be compared to the predicate. This would be easy when this were just a list, then I would do something like this:

all (<= (getCharOccurrence (head word) (getCharOccurrences letters))) [0..10]

But the problem is: I dont have a list of results like this, I need to compare it to the result of:

(getCharOccurrence (head word) (getCharOccurrences letters))

I figured that I could apply this function to every character in the 'word' char list with the 'map' function, but I dont know how to use it. I started like this:

map (getCharOccurrence (head word) (getCharOccurrences word)) word

But that's wrong.

So what I (think I) need: apply the above function to all characters of the 'word' char list, and compare it to the predicate.

But maybe I'm just think the wrong way. I'm an absolute Haskell/functional programming newbie. Please help me out :-)

Upvotes: 0

Views: 3505

Answers (3)

Daniel Wagner
Daniel Wagner

Reputation: 153352

Using the multiset package:

import Data.MultiSet
compareAll as bs = fromList as `isSubsetOf` fromList bs

or:

import Data.Function
import Data.MultiSet
compareAll = isSubsetOf `on` fromList

Upvotes: 3

niklon
niklon

Reputation: 176

So from what I understand you have a string word with the word you would like to form and a list of chars letters representing the tiles at your disposal. You want to check whether the word may be formed by the tiles or not.

Here I'm assuming the functions you've mentioned have the types

getCharOccurrence :: Char -> [(Char, Integer)] -> Integer
getCharOccurrences :: [Char] -> [(Char, Integer)]

First, you need to modify hasLetters' to take a Char parameter instead of using head word:

hasLetters' :: Char -> [Char] -> [Char] -> Bool
hasLetters' c word letters = (getCharOccurrence c (getCharOccurrences word)) <= (getCharOccurrence c (getCharOccurrences letters))

Then you can combine the above to a master function (let's call it sufficientTiles) with 

sufficientTiles :: [Char] -> [Char] -> Bool
sufficientTiles word letters = and $ map (\c -> hasLetters' c word letters) word

What we've done here is to map the hasLetter' function to each character of word. This will give us a list of Bools. We then use and to check that all elements of that list are True.

Upvotes: 2

Thomas M. DuBuisson
Thomas M. DuBuisson

Reputation: 64750

So I think I understand that you want to compare two lists. The test passes if the second list has at least as many of each element as the first list. Thus, you need a constraint of at least equality but order would help.

There are many solutions, the one that comes to mind first is sort each list, group and count the unique elements, and ensure all results are <=:

someCompare a b = let op :: String -> [(Char,Int)]
                      op = map (head &&& length) . group . sort
                  in [c <= k | (x,c) <- op a, k <- maybeToList (lookup x (op b))]

Or you can use a map of counters and union the two maps:

someCompare2 a b =
        let op = foldl' (\m c -> Map.insertWith (+) c 1 m) Map.empty
        in all (<= 0) . Map.elems $ Map.unionWith (+) (op a) (Map.map negate $ op b)

Etc etc.

Upvotes: 1

Related Questions