昨日の虫食い算

昨日の虫食い算[id:dachs_hippo:20080315]をHaskellで書いてみました．

{-
mushikui.hs
-}
import List

f::[Int]->[Int]->[[String]]
f ns = concat . map (\y -> (map (\x->[show x, show y, show $ x*y ]) ns))

g::[Int]->[Int] -> [([String],String)]
g ns = (map (\x -> (x, sort $ concat x))) . (f ns)

h::[Int] -> [Int] -> [String]
h ns =  (map (result.fst)) . (filter (fulldigit.snd) ) . (g ns) 

fulldigit::String -> Bool
fulldigit "0123456789" = True
fulldigit _            = False

result::[String]->String
result xs = ((xs!!0) ++ " * " ++ (xs!!1) ++ " = " ++ (xs!!2))

とにかく，ghciで実行．

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.6.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Prelude> :l mushikui.hs
[1 of 1] Compiling Main             ( mushikui.hs, interpreted )
*Main> mapM_ putStrLn $ h [1000..9999] [2..9]
5694 * 3 = 17082
6819 * 3 = 20457
6918 * 3 = 20754
8169 * 3 = 24507
9168 * 3 = 27504
3907 * 4 = 15628
7039 * 4 = 28156
9127 * 4 = 36508
5817 * 6 = 34902
3094 * 7 = 21658
4093 * 7 = 28651
9304 * 7 = 65128
9403 * 7 = 65821

けど，美しくない．中間処理だけの関数が多いし，無駄に大きいリストを作ってる気がします（実際は遅延評価のおかげで作ってないのかもしれませんが）．最初に[1000..9999] x [2..9]の値を全部計算して，それを最後の方まで引きずってるのが嫌です．先に一覧を作っておいて，それから必要なものを取り出すという流れは自然だと思うのですが，それならば一覧を作りながら必要なものだけを載せればよいのです．

{-
mushikui2.hs
-}
import List

f::[Int]->[Int]->[[Int]]
f ns  = (filter digitcheck) . concat . (map (\y -> (map (\x-> [x, y, x*y]) ns)))

digitcheck::[Int] -> Bool
digitcheck =  fulldigit . sort . concat . (map show)

fulldigit::String -> Bool
fulldigit "0123456789" = True
fulldigit _            = False

result::[Int]->String
result xs = (show(xs!!0) ++ " * " ++ show(xs!!1) ++ " = " ++ show(xs!!2))

実行してみます．

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.6.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Prelude> :l mushikui.hs
[1 of 1] Compiling Main             ( mushikui2.hs, interpreted )
*Main> mapM_ (putStrLn.result) $ f [1000..9999] [2..9]
5694 * 3 = 17082
6819 * 3 = 20457
6918 * 3 = 20754
8169 * 3 = 24507
9168 * 3 = 27504
3907 * 4 = 15628
7039 * 4 = 28156
9127 * 4 = 36508
5817 * 6 = 34902
3094 * 7 = 21658
4093 * 7 = 28651
9304 * 7 = 65128
9403 * 7 = 65821

体感は大差ないから多分実際には大きな一覧はできてないんじゃないかとは思いますが，ま，ちょっとだけ綺麗になった気がするのでよしとします．

(追記)2008/3/39
リスト内包表記で書けばmapの二段重ねはいらないですね