[Haskell-beginners] problems using bytestrings

[Daniel Fischer]

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 ...