Haskell - リスト - map と filter(リスト内包表記、コンビネータ)

関数プログラミング入門
原著

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• Haskell (プログラミング言語)
• Haskell Platform(ghci)(処理系)

関数プログラミング入門(Richard Bird (著)、山下伸夫 (翻訳)、オーム社)の第4章(リスト)、4.3(map と filter)、練習問題4.3.1、4.3.2、4.3.3、4.3.4、4.3.5、4.3.6、4.3.7、4.3.8、4.3.9、4.3.10、4.3.11を取り組んでみる。

練習問題4.3.1、4.3.2、4.3.3、4.3.4、4.3.5、4.3.6、4.3.7、4.3.8、4.3.9、4.3.10、4.3.11

コード(Emacs)

-- 4.3.1
square :: (Num a) => a -> a
square x = x * x

a :: [[Integer]]
a = map (map square) [[1, 2], [3, 4, 5]]

-- 4.3.2
-- map f undefined = undefined
b = map undefined []

-- 4.3.3
f :: [a -> b] -> [[a] -> [b]]
f = map map

fs :: (Show a, Num a) => [a -> String]
fs = [\x -> show x, \x -> show (x + 1)]

-- 4.3.4
-- map f (undefined ++ ys)
-- = map f undefined
-- = undefined

-- map f ([] ++ ys)
-- = map f xs
-- map f [] ++ map f ys
-- = [] ++ map f ys
-- = map f ys

-- map f ((x:xs) ++ ys)
-- = map f (x:(xs ++ ys))
-- = (f x):(map f (xs ++ ys))
-- = (f x):(map f xs ++ map f ys)
-- = (f x):(map f xs) ++ map f ys
-- = map f (x:xs) ++ map f ys

-- map f . concat undefined
-- = map f undefined
-- = undefined

-- concat . map (map f) undefined
-- = concat undefined
-- = undefined

-- map f . concat []
-- = map f []
-- = []
-- concat . map (map f) []
-- = concat []
-- = []

-- map f . concat (xs:xss)
-- = map f (xs ++ concat xss)
-- = map f xs ++ map f (concat xss)
-- = map f xs ++ (concat ((map (map f) xss)))
-- = concat ((map f xs):(map (map f) xss))
-- = concat (map (map f) (xs:xss))
-- = concat . map (mapf) (xs:xss)

-- 4.3.5
inits :: [a] -> [[a]]
inits [] = [[]]
inits (x:xs) = (init (x:xs)):(inits xs)

g :: (a -> a) -> [a] -> [[a]]
g f xs = inits (map f xs)

h :: (a -> a) -> [a] -> [[a]]
h f xs = map (map f) (inits xs)

c = g square [1..10]
d = h square [1..10]

-- 4.3.6
filter :: (a -> Bool) -> [a] -> [a]
filter p = concat . map box
  where box x = if p x
                then [x]
                else []

-- 4.3.7
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p [] = []
takeWhile p (x:xs) = if p x
                     then x:(Main.takeWhile p xs)
                     else []

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p [] = []
dropWhile p (x:xs) = if p x
                     then Main.dropWhile p xs
                     else (x:xs)

-- 4.3.8
-- xs == ys
-- xs == []
-- length ys == 1

-- 4.3.9
pairs :: Integer -> [(Integer, Integer)]
pairs n = [(x, y) | x <- [1..n], y <- [x..n]]

-- 4.3.10
f1 :: Integer -> [(Integer, Integer, Integer, Integer)]
f1 n = [(a, b, c, d) |
        a <- [1..n], b <- [a..n], c <- [a+1..n], d <- [c..n],
        a ^ 2 + b ^ 2 == c ^ 2 + d ^ 2]

-- 4.3.11
f2 :: Integer -> [(Integer, Integer)]
f2 n = concat ps
  where xs = Prelude.filter odd [1..n]
        f y = map g xs
          where g x = (x, y)
        ps = map f [1..n]

f3 :: Integer -> [(Integer, Integer)]
f3 n = concat ps
  where f x = map g [1..n]
              where g y = if odd x
                          then [(x, y)]
                          else []
        ps = concat (map f [1..n])

-- 2つの式の評価コスト
-- f2 odd x: n
-- f3 odd x: n * n

main :: IO ()
main = do
  print (a == [[1, 4], [9, 16, 25]])
  print (null b)
  print ((f fs !! 0) [1, 2])
  print ((f fs !! 1) [1, 2])
  print (inits [1..10])
  print c
  print (c == d)
  print (Main.filter even [1..10])
  print (Main.takeWhile even [2, 4, 6, 1, 5, 6])
  print (Main.dropWhile even [2, 4, 6, 1, 5, 6])
  print (pairs 5)
  print (f1 20)
  print (f2 5)
  print (f3 5)

入出力結果(Terminal, ghci, runghc)

$ runghc sample3.hs
True
True
["1","2"]
["2","3"]
[[1,2,3,4,5,6,7,8,9],[2,3,4,5,6,7,8,9],[3,4,5,6,7,8,9],[4,5,6,7,8,9],[5,6,7,8,9],[6,7,8,9],[7,8,9],[8,9],[9],[],[]]
[[1,4,9,16,25,36,49,64,81],[4,9,16,25,36,49,64,81],[9,16,25,36,49,64,81],[16,25,36,49,64,81],[25,36,49,64,81],[36,49,64,81],[49,64,81],[64,81],[81],[],[]]
True
[2,4,6,8,10]
[2,4,6]
[1,5,6]
[(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)]
[(1,7,5,5),(1,8,4,7),(1,12,8,9),(1,13,7,11),(1,17,11,13),(1,18,6,17),(1,18,10,15),(2,9,6,7),(2,11,5,10),(2,14,10,10),(2,16,8,14),(2,19,13,14),(3,11,7,9),(3,14,6,13),(3,16,11,12),(3,19,9,17),(4,13,8,11),(4,17,7,16),(4,18,12,14),(4,19,11,16),(5,14,10,11),(5,15,9,13),(5,20,8,19),(5,20,13,16),(6,17,10,15),(7,17,13,13),(7,19,11,17),(8,19,13,16),(9,20,15,16)]
[(1,1),(3,1),(5,1),(1,2),(3,2),(5,2),(1,3),(3,3),(5,3),(1,4),(3,4),(5,4),(1,5),(3,5),(5,5)]
[(1,1),(1,2),(1,3),(1,4),(1,5),(3,1),(3,2),(3,3),(3,4),(3,5),(5,1),(5,2),(5,3),(5,4),(5,5)]
$