[shangaslammi]

Here'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)