Haskell - Data.Mapモジュール(keys, fromList, foldWithKey関数(疎ベクトルの和、ドット積))

すごいHaskellたのしく学ぼう!
(オーム社)
Miran Lipovača (著)
田中 英行 村主 崇行 (翻訳)
[Kindle版]

開発環境

• OS X Mavericks - Apple(OS)
• BBEdit - Bare Bones Software, Inc., Emacs (Text Editor)
• Haskell (純粋関数型プログラミング言語)
• GHC (The Glasgow Haskell Compiler) (処理系)
• The Haskell Platform (インストール方法、モジュール等)

初めてのコンピュータサイエンス(Jennifer Campbell、Paul Gries、Jason Montojo、Greg Wilson(著)長尾 高弘(翻訳))の9章(集合と辞書)、9.5(練習問題)、14.をHaskellで解いてみる。

その他参考書籍

• プログラミングHaskell (オーム社) Graham Hutton(著) 山本 和彦(翻訳)
• Real World Haskell―実戦で学ぶ関数型言語プログラミング (オライリージャパン) Bryan O'Sullivan John Goerzen Don Stewart(著) 山下 伸夫 伊東 勝利 株式会社タイムインターメディア(翻訳)

9.5(練習問題)、14.

コード(BBEdit)

Sample.hs

{-# OPTIONS -Wall -Werror #-}
import qualified Data.Map as Map
import System.Random

main :: IO ()
main = mapM_ putStrLn $ map (\(d1, d2) -> "d1:        " ++ show d1 ++
                                          "\nd2:        " ++ show d2 ++
                                          "\nsparseAdd: " ++
                                          (show $ sparseAdd d1 d2) ++
                                          "\nsparseDot: " ++
                                          (show $ sparseDot d1 d2)) $
                            map (\x -> (mkMap x, mkMap $ x + 10))
                                [1..10]

mkMap :: Int -> Map.Map Int Int
mkMap n = Map.fromList $
    zip (take (fst $ randomR ((1 :: Int), (10 :: Int)) $ mkStdGen n)
              (randomRs ((1 :: Int), (10 :: Int)) $ mkStdGen n))
        (take (fst $ randomR ((1 :: Int), (10 :: Int)) $ mkStdGen $ n + 10)
              (randomRs ((1 :: Int), (10 :: Int)) $ mkStdGen $ n + 10))

sparseAdd :: (Ord k, Num a) => Map.Map k a -> Map.Map k a -> Map.Map k a
sparseAdd m1 m2 = Map.fromList $
    let ks1 = Map.keys m1
        ks2 = Map.keys m2
    in foldr (\k acc -> if elem k ks1 && elem k ks2 then
                            (k, (m1 Map.! k) + (m2 Map.! k)):acc
                        else
                            if elem k ks1 then
                                (k, (m1 Map.! k)):acc
                            else
                                (k, (m2 Map.! k)):acc)
             [] (ks1 ++ ks2)

sparseDot :: (Ord k, Num a) => Map.Map k a -> Map.Map k a -> a
sparseDot m1 m2 =
    let ks2 = Map.keys m2
    in Map.foldWithKey (\k a acc -> if elem k ks2 then
                                        a * (m2 Map.! k) + acc
                                    else
                                        acc)
                       0 m1

入出力結果(Terminal, runghc)

$ runghc Sample.hs
d1:        fromList [(1,1),(7,10),(8,9),(9,6),(10,10)]
d2:        fromList [(1,10),(4,8),(6,4),(8,8),(9,7),(10,2)]
sparseAdd: fromList [(1,11),(4,8),(6,4),(7,10),(8,17),(9,13),(10,12)]
sparseDot: 144
d1:        fromList [(2,1)]
d2:        fromList [(1,7),(2,2)]
sparseAdd: fromList [(1,7),(2,3)]
sparseDot: 2
d1:        fromList [(4,5),(5,7),(6,4),(8,2),(10,10)]
d2:        fromList [(2,4),(4,1),(5,5),(6,6),(7,6),(10,2)]
sparseAdd: fromList [(2,4),(4,6),(5,12),(6,10),(7,6),(8,2),(10,12)]
sparseDot: 84
d1:        fromList [(1,7),(2,8),(4,8),(6,9),(7,8),(10,10)]
d2:        fromList [(2,1),(6,9),(7,6),(8,4),(9,2),(10,2)]
sparseAdd: fromList [(1,7),(2,9),(4,8),(6,18),(7,14),(8,4),(9,2),(10,12)]
sparseDot: 157
d1:        fromList [(2,1),(3,7),(4,1)]
d2:        fromList [(1,3),(4,4),(7,1)]
sparseAdd: fromList [(1,3),(2,1),(3,7),(4,5),(7,1)]
sparseDot: 4
d1:        fromList [(2,3),(4,6),(5,6),(7,6),(8,8),(10,10)]
d2:        fromList [(3,4),(5,8),(6,6),(8,8),(10,2)]
sparseAdd: fromList [(2,3),(3,4),(4,6),(5,14),(6,6),(7,6),(8,16),(10,12)]
sparseDot: 132
d1:        fromList [(1,9),(2,2)]
d2:        fromList [(2,2),(9,6)]
sparseAdd: fromList [(1,9),(2,4),(9,6)]
sparseDot: 4
d1:        fromList [(1,3),(6,2),(10,2)]
d2:        fromList [(2,2),(3,2),(6,6),(9,10)]
sparseAdd: fromList [(1,3),(2,2),(3,2),(6,8),(9,10),(10,2)]
sparseDot: 12
d1:        fromList [(1,2),(3,4),(5,1),(6,7),(8,3),(9,6),(10,2)]
d2:        fromList [(1,7),(2,3),(3,7),(4,7),(5,7),(6,4),(7,7),(10,4)]
sparseAdd: fromList [(1,9),(2,3),(3,11),(4,7),(5,8),(6,11),(7,7),(8,3),(9,6),(10,6)]
sparseDot: 85
d1:        fromList [(2,1),(4,4),(5,9),(8,7)]
d2:        fromList [(1,7),(4,4),(7,9),(9,3)]
sparseAdd: fromList [(1,7),(2,1),(4,8),(5,9),(7,9),(8,7),(9,3)]
sparseDot: 16
$

慣れるまでは{-# OPTIONS -Wall -Werror #-}の記述を消さずに細かく型を指定していくことに。