given an input 'dictionary' (a list of words) and a string, determine whether the string is an arbitrary concatenation of the words in the dictionary

get_dictionary_concatenation.hs

import System.Environment
import Control.Applicative
import Data.Maybe
import Data.List
import qualified Data.Text as T
import qualified Data.Text.IO as I
import qualified Trie as T

getDictionaryConcatenation :: Ord a => [a] -> T.Trie a -> Maybe [[a]]
getDictionaryConcatenation [] t = Just []
getDictionaryConcatenation xs t
  | null pairs = Nothing
  | otherwise = (\(p, (Just ss)) -> Just (p : ss)) $ head pairs
  where
    prefixes = T.prefixesFor xs t
    suffixes = map (fromJust . flip stripPrefix xs) prefixes
    concats = map (flip getDictionaryConcatenation t) suffixes
    pairs = sortBy (\(_, Just a) (_, Just b) -> length a `compare` length b) $
              filter (isJust . snd) $ zip prefixes concats

loadDictionary :: IO (T.Trie Char)
loadDictionary = do
  words <- T.lines <$> T.toLower <$> I.readFile "/usr/share/dict/words"
  let dict = T.fromList $ map T.unpack words
  putStrLn "loaded dictionary"
  return dict

main = do
  args <- getArgs
  if length args /= 1
    then putStrLn "you must give a string"
    else do
      dict <- loadDictionary
      putStrLn $ show $ getDictionaryConcatenation (head args) dict

is_dict_concat.rb

class Trie

  Insertion = Struct.new(:pos, :str) do

    def finished?
      pos == str.length
    end

    def current_char
      char_at(pos)
    end

    def char_at(index)
      str.each_char.to_a[index]
    end

    def incr
      obj = self.clone
      obj.pos += 1
      obj
    end

  end

  def initialize
    @nexts = Hash.new
    @word = nil
  end

  def add(word)
    ins = Insertion.new(0, word)
    _add(ins)
  end

  def match_prefixes_for(str)
    ins = Insertion.new(0, str)
    _match_prefixes_for(ins).compact
  end

  protected

  def _add(ins)
    if ins.finished?
      @word = ins.str
    else
      @nexts[ins.current_char] ||= Trie.new
      @nexts[ins.current_char]._add(ins.incr)
    end
  end

  def _match_prefixes_for(ins)
    words = [@word]
    if !ins.finished? && child = @nexts[ins.current_char]
      words += child._match_prefixes_for(ins.incr)
    end
    words
  end

end

def string_is_dict_combo(dict, str)
  trie = Trie.new
  dict.each { |word| trie.add(word) }

  func = lambda do |str|
    matched_words = trie.match_prefixes_for(str)
    matched_words.each do |word|
      if word == str # we finished with the input
        return true
      elsif word.length < str.length
        result = func[str[word.length..-1]]
        return true if result
      end
    end
    return false
  end

  func[str]
end

puts string_is_dict_combo(["foo", "bar", "baro", "baz"], "bazbarobarfootbaz")

Trie.hs

module Trie (
  Trie,
  empty,
  fromList,
  insert,
  prefixesFor
) where

import Data.Maybe
import Data.List (foldr)
import qualified Data.Map as M

data Trie a = Trie (Maybe [a]) (M.Map a (Trie a))
            | Leaf
              deriving Show

-- create a new, empty Trie
empty :: Ord a => Trie a
empty = Trie Nothing M.empty

-- create a new Trie from a list
fromList :: Ord a => [[a]] -> Trie a
fromList xs = foldr (\x t -> insert x t) empty xs

-- insert a list into a Trie
insert :: Ord a => [a] -> Trie a -> Trie a
insert xs t = insert' xs xs t

insert' [] xs' (Trie _ m) = Trie (Just xs') m
insert' (x:xs) xs' (Trie s m) = Trie s m'
  where
    next = M.findWithDefault (Trie Nothing M.empty) x m
    m' = M.insert x (insert' xs xs' next) m

-- return all the prefixes of the given list that are present in the Trie
prefixesFor :: Ord a => [a] -> Trie a -> [[a]]
prefixesFor xs t = map fromJust $ filter isJust $ prefixesFor' xs t

prefixesFor' _ Leaf = []
prefixesFor' [] (Trie s _) = [s]
prefixesFor' (x:xs) (Trie s m) = s : prefixesFor' xs (M.findWithDefault Leaf x m)