时间戳

首页 > 解决方案 > Make map return Nothing if one of the elements producing Nothing

haskell - Make map return Nothing if one of the elements producing Nothing

问题描述

I am trying to implement Huffman compression in Haskell for learning purposes. So far I can successfully create the correct tree for a given String and I can get the correct path to a character from a specific tree. The signature of that function is like this:

getPath :: HuffmanTree -> Char -> Maybe String

It returns a Just String where '0' represents the left and '1' the right branch. If the character isn't contained in the tree it returns Nothing. My next step is to pass it a whole String and turn it to an encoded String of 1s and 0s. The method should return Nothing, if one of the characters is not found in the tree, accordingly the function signature should look like this:

encode :: HuffmanTree -> String -> Maybe String

My current Method of doing this is like this:

encode tree str =
let encodings = map (\e -> getPath tree e) str
in
    if elem Nothing encodings
    then Nothing
    else
        let encodings' = map fromJust encodings
        in Just (foldl (++) "" encodings')

But this doesn't seem to be a very elegant way of solving this. I know, I can abort everything if the first getPath returns Nothing, so every evaluation after that is unnecessary. I feel like, there is a fancy monadic way to do this right, but I couldn't think of one and I don't really know what to search for. Or is this the right way and just let laziness take care of everything?

标签： haskellfunctional-programming

解决方案

确实有一种单子方式可以做到这一点，而且它并不是特别花哨。这正是应用程序的Maybe目的，因此您可以使用traverse：

encode tree str = fmap concat $ traverse (\e -> getPath tree e) str

或短

encode tree = fmap concat . traverse (getPath tree)

整齐，嗯？

推荐阅读