しりとり

programming haskell

なんか煮詰まったので息抜きに ここの問題 をひとつ解いてみる．

しりとり：
1. 文字列のリストの要素全てを使ってしりとりが完結するかを判定
2. 最長のしりとりを出力

とりあえずいけるところまでしりとりさせる．
OCaml でやろうかと思ったけどバックトラックは Haskell が簡単そうなのでそうする．

(追記: last と head は既にあるよとの指摘をもらったので直しました．)



import Data.List

import Control.Monad
shiritori :: [String] -> String

shiritori [] = [[]]

shiritori [w] = w

shiritori ws = do w <- ws

                  ws' <- shiritori $ delete w ws

                  if (last w) == (head $ head ws')

                     then return $ w : ws'

                     else return [w]
ふむ，昨日の順列生成とほとんど同じだなぁ．
shiritori では取り出した単語の最後の文字とこれから作る単語のリストの先頭の頭の文字を比較して，異なればそこで終了させる．
多分素直な実装だと思う．

1番は最長の長さが元の配列の長さと同じであればよい．



maxLength :: String -> Int

maxLength ss = foldr (\x max' -> max max' $ length x) 0 ss
enableShiritori :: [String] -> Bool

enableShiritori ws = length ws == (maxLength $ shiritori ws)

2. は結果から最長のものだけを取り出せば良い

shiritori' :: [String] -> String

shiritori' ws = let ws' = shiritori ws 

                in

                  filter (\x -> length x == maxLength ws') ws'

書いてから 後輩 Haskeller の解答 を見たけど StateT はまだ良く分かりません...