4 ms·
Just for fun I decided to rewrite his first version in Haskell. This is probably not idiomatic, though. segment_string :: String -> Set String -> Maybe Strin
by nandemo 15y ago
Just for fun I decided to rewrite his first version in Haskell. This is probably not idiomatic, though.
segment_string :: String -> Set String -> Maybe String
segment_string [] _ = Nothing
segment_string str dict =
if str `member` dict
then Just str
else let pairs = zip (inits str) (tails str)
pairInDict (x, y) = x `member` dict && y `member` dict in
do (x, y) <- find pairInDict pairs
Just (x ++ " " ++ y)
- ottbot 15y agohttp://www.codinghorror.com/blog/2007/02/fizzbuzz-the-programmers-stairway-to-heaven.html http://www.codinghorror.com/blog/2007/02/fizzbuzz-the-progra...
- nandemo 15y agoSo what? This problem (the full version) is more complex than FizzBuzz. Besides, I'm not pasting code here to prove that I can program, but to show how the solution looks like in Haskell.
- eru 15y agoYes, doesn't strike me as idiomatic. But I can't come up with a better version on the spot.
- zohebv 15y agoHow about this, this will compute more than pairs <pre><code> let dict = Data.Set.fromList["apple", "pie", "bread", "applepie", "piebread"] let fn q = concat.Data.List.map (\(x,y) -> if (member x dict) then if y == "" then [[x]] else Data.List.map (x:) (fn y) else [] ) $ tail $ zip (inits q) (tails q) fn "applepiebread" [["apple","pie","bread"],["apple","piebread"],["applepie","bread"]] </code></pre>
- shangaslammi 15y agoHere's my Haskell attempt (both naive recursive backtrack and dynamic programming version): type Dict = Set String hasWord :: Dict -> String -> Bool hasWord = flip Set.member fmtWords :: [[String]] -> Maybe String fmtWords = fmap (intercalate " ") . listToMaybe splitWordsSimple :: Dict -> String -> Maybe String splitWordsSimple dct = fmtWords . go where go [] = return [] go s = do (i,t) <- zip (inits s) (tails s) guard $ hasWord dct i (i:) <$> go t splitWordsDP :: Dict -> String -> Maybe String splitWordsDP dct s = fmtWords $ a ! 0 where a = listArray (0, len) $ map f [0..len-1] ++ [[[]]] len = length s f i = do l <- [1..len-i] let w = take l $ drop i s guard $ hasWord dct w (w:) <$> a ! (i+l)