Reputation: 12496
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
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
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
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