Am Dienstag 19 Januar 2010 22:34:41 schrieb Joe Van Dyk:
Thanks for the response. I was getting confused -- I'm used to thinking about a String as being its own type, instead of being an array of chars.
Lists are NOT arrays. If it was not just loose language on your side, learn the distinction. List indexing (list !! k) is O(min k (length list)), array indexing is O(1). An array knows its size (resp. it can easily be calculated from the known bounds), a list does not. length list is O(length list). If you're not aware of the differences, sooner rather than later, you'll get bitten by a gigantic performance bug.
I now have:
anagrams :: [BS.ByteString] -> [[BS.ByteString]] anagrams words = sorted_anagrams where sorted_anagrams = sortBy (flip $ comparing length) get_anagrams get_anagrams = Map.elems $ foldl' insert_word Map.empty words insert_word map word = Map.insertWith' (++) sorted_word [word] map sorted_word word = BS.pack . sort . BS.unpack $ word
But get this error:
anagram.hs:12:27: No instance for (Ord (BS.ByteString -> BS.ByteString)) arising from a use of `Map.insertWith'' at anagram.hs:12:27-69 Possible fix: add an instance declaration for (Ord (BS.ByteString -> BS.ByteString)) In the expression: Map.insertWith' (++) sorted_word [word] map In the definition of `insert_word': insert_word map word = Map.insertWith' (++) sorted_word [word] map In the definition of `anagrams': anagrams words = sorted_anagrams where sorted_anagrams = sortBy (flip $ comparing length) get_anagrams get_anagrams = Map.elems $ foldl' insert_word Map.empty words insert_word map word = Map.insertWith' (++) sorted_word [word] map sorted_word word = BS.pack . sort . BS.unpack $ word
is sorted_word returning a function?
sorted_word *is* a function. What you want in insert_word is (sorted_word word), i.e. insert_word map word = Map.insertWith' (++) (sorted_word word) [word] map Since you forgot to apply sorted_word to the ByteString, it tries to use the function sorted_word :: ByteString -> ByteString as a key, but it can't find the instance Ord (ByteString -> ByteString) where ...