しりとり

Haskell

勉強会でのネタ。与えられた語彙を全て使ってしりとりができるかどうかを判定するもの。
shiritori は無理に StateT を使ったもの。
shiritori2 は、順列を作ったあとにしりとりができる並びのものだけを取り出すという素直な実装。

import System (getArgs)
import Control.Monad.State
import Data.List (delete)

-- solution 1
shiritori :: Int -> StateT ([String], [String]) [] ()
shiritori 0 = return ()
shiritori n =
    do (w:ws, v) <- get
       lift [(a:w:ws, delete a v) | a<-v, null w || last w == head a] >>= put
       shiritori (n-1)
main = do args <- getArgs
          mapM_ (putStrLn.unwords.reverse.fst) $
                execStateT (shiritori $ length args) ([""],args)

-- solution 2
perm l = perm' ([],l)
    where perm' (a,[]) = return a
          perm' (a,b)  = do c <- b
                            perm' (c:a, delete c b)
shiritori2 ws = filter connectable $ perm ws
    where connectable []      = True
          connectable [a]     = True