1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@syuuu

Haskell でリスト全体を2乗する7個ぐらいの方法

1
Last updated at Posted at 2022-08-06

概要

Functor, Applicative, Monad の動きを整理する一貫でまとめてみた。

環境

  • GHC 8.4.4 (Ubuntu 18.04 LTS)

Input と Output

入力

[1..]

出力

[1,4,9,16,25]

リスト内包表記

今回は、これが一番シンプルですね。
ghci で -Wall を付けると型指定がされていない場合は警告がでます。[1..] の型指定は致し方ないですね。

main :: IO ()
main = do
  print $ take 5 $ [x * x | x <- ([1..] :: [Int])]

再帰的な関数

2乗の部分は、 x * x と x ^ (2::Int) (または Integer) と2通りできるのですが、後者の型は明示的に指定するように言われるので、x * xがシンプルな書き方になります。(前者(x*x)は引数の型 Int と Integer に合わせて計算してくれますが、後者 x ^ (2::Int) だと Int か Integer 決め打ちになってしまいます。)

sqList :: (Integral t) => [t] -> [t]
sqList [] = []
sqList (x:xs) = (x * x):sqList(xs)

main :: IO ()
main = do
  print $ take 5 $ sqList ([1..] :: [Int])

map

map はリスト専用ですね。

main :: IO ()
main = do
  -- Using `map`
  print $ take 5 $ map (\x -> x * x) ([1..] :: [Int])
  print $ take 5 $ map (^(2::Int)) ([1..] :: [Int])

fmap

fmap はリスト以外でも使えるものです。 fmap を使う場合は同じ形になっています。
fmap の別名の中置演算子 <$> が用意されていて、同じように結果を出力できます。

main :: IO ()
main = do
  -- Using `fmap`
  print $ take 5 $ fmap (\x -> x * x) ([1..] :: [Int])
  -- using an infix synonym(<$>) for `Data.Functor.fmap`.
  print $ take 5 $ (\x -> x * x) <$> ([1..] :: [Int])

Applicative

1つ目が pure (^(2::Int)) というモナドで1つの計算式をリストに関連付けています。
2つ目は リストモナドを使っています。リストモナドの場合は、演算をリストに適用できますが、今回は1つだけ指定しています。

main :: IO ()
main = do
  -- Applicative 1
  print $ take 5 $ pure (^(2::Int)) <*> ([1..] :: [Int])
  -- Applicative 2
  print $ take 5 $ [(^(2::Int))] <*> ([1..] :: [Int])

Monad

sqListMonad :: Int -> [Int]
sqListMonad n = do
  value <- [1 .. n]
  return (value^(2::Int))

main :: IO ()
main = do
  -- With Monad 1
  print $ take 5 $ ([1..] :: [Int]) >>= \x -> pure (x * x)
  -- With Monad 2
  print $ take 5 $ do {value <- ([1..] :: [Int]); pure (value ^ (2::Int))}
  -- With Monad 3
  print $ sqListMonad 5
  -- With Monad 4
  print $ take 5 $ (\n -> pure (n * n)) =<< ([1..] :: [Int])

foldr

main :: IO ()
main = do
  print $ take 5 $ foldr (\x xs -> (x * x) : xs) [] ([1..] :: [Int])

おまけ: foldrで無限リストにすると失敗するケース

foldr では、関数次第ですが、無限リストを扱えます。
同じ結果を返却するコードですが、無限リストを対象とする場合は評価順序(遅延評価 or not)によって振舞が異なります。

この辺り、Haskell らしい内容ですね。

失敗するコード例

コード

\x y -> (x * x) : y に関し、trace で show y をしているので、後続のリスト y の評価が優先されます。

import Debug.Trace

traceMyFoldrLH :: (Show a, Show b) => (a -> b -> b) -> b -> [a] -> b
traceMyFoldrLH _ z [] =
  trace("traceMyFoldrLH f " ++ (show z) ++ " [] = " ++ (show z))
  $ z
traceMyFoldrLH f z (x:xs) =
  trace("traceMyFoldrLH f " ++ (show z) ++ " (" ++ (show x) ++ ":[..]) = f " ++ (show x) ++ " (traceMyFoldrLH f " ++ (show z) ++ " [..])")
  $ f x (traceMyFoldrLH f z xs)

main :: IO ()
main = do
  putStrLn "\n-- take 5 $ traceMyFoldrLH (\\x y -> trace(\"(\\x y -> (x * x) : y) = \" ++ (show (x * x)) ++ \":\" ++ show y) $ (x * x) : y) [] ([1..6] :: [Int])"
  print $ take 5
        $ traceMyFoldrLH (\x y -> trace("(\\x y -> (x * x) : y) = " ++ (show (x * x)) ++ ":" ++ show y) $ (x * x) : y) [] ([1..6] :: [Int])

参考までにトレースを取り除くと次のようなコードになります。このコードは無限リストに対して問題なく動作します。

import Debug.Trace

traceMyFoldrLH :: (Show a, Show b) => (a -> b -> b) -> b -> [a] -> b
traceMyFoldrLH _ z [] = z
traceMyFoldrLH f z (x:xs) = f x (traceMyFoldrLH f z xs)

main :: IO ()
main = do
  putStrLn "\n-- take 5 $ traceMyFoldrLH (\\x y -> (x * x) : y) [] ([1..6] :: [Int])"
  print $ take 5
        $ traceMyFoldrLH (\x y -> (x * x) : y) [] ([1..6] :: [Int])

実行結果

1 を呼んだあと、後続の y の評価をするのために、[2, 3, 4, 5, 6] を 先に 評価しようとします。
そのため、無限リストにすると、先に末尾を見に行くので終了しません。

foldr 自体は後ろの要素から評価するコードなので、 ある意味見かけ上のコード通りの評価順 ではあります。

-- take 5 $ traceMyFoldrLH (\x y -> trace("(\x y -> (x * x) : y) = " ++ (show (x * x)) ++ ":" ++ show y) $ (x * x) : y) [] ([1..6] :: [Int])
traceMyFoldrLH f [] (1:[..]) = f 1 (traceMyFoldrLH f [] [..])
traceMyFoldrLH f [] (2:[..]) = f 2 (traceMyFoldrLH f [] [..])
traceMyFoldrLH f [] (3:[..]) = f 3 (traceMyFoldrLH f [] [..])
traceMyFoldrLH f [] (4:[..]) = f 4 (traceMyFoldrLH f [] [..])
traceMyFoldrLH f [] (5:[..]) = f 5 (traceMyFoldrLH f [] [..])
traceMyFoldrLH f [] (6:[..]) = f 6 (traceMyFoldrLH f [] [..])
traceMyFoldrLH f [] [] = []
(\x y -> (x * x) : y) = 36:[]
(\x y -> (x * x) : y) = 25:[36]
(\x y -> (x * x) : y) = 16:[25,36]
(\x y -> (x * x) : y) = 9:[16,25,36]
(\x y -> (x * x) : y) = 4:[9,16,25,36]
(\x y -> (x * x) : y) = 1:[4,9,16,25,36]

失敗するコードの修正例

コード

trace で y の内容を文字列化するのをやめました。

import Debug.Trace

traceMyFoldrLH :: (Show a, Show b) => (a -> b -> b) -> b -> [a] -> b
traceMyFoldrLH _ z [] =
  trace("traceMyFoldrLH f " ++ (show z) ++ " [] = " ++ (show z))
  $ z
traceMyFoldrLH f z (x:xs) =
  trace("traceMyFoldrLH f " ++ (show z) ++ " (" ++ (show x) ++ ":[..]) = f " ++ (show x) ++ " (traceMyFoldrLH f " ++ (show z) ++ " [..])")
  $ f x (traceMyFoldrLH f z xs)

main :: IO ()
main = do
  putStrLn "\n-- take 5 $ traceMyFoldrLH (\\x y -> trace(\"(\\x y -> (x * x) : y) = \" ++ (show (x * x)) ++ \":y\") $ (x * x) : y) [] ([1..] :: [Int])"
  print $ take 5
        $ traceMyFoldrLH (\x y -> trace("(\\x y -> (x * x) : y) = " ++ (show (x * x)) ++ ":y") $ (x * x) : y) [] ([1..] :: [Int])

実行結果

トレースと結果 [1,4,9,16,25] が混ざって [1 ,4 ,9 ,16 ,25] が割り込んでいます。ただ、評価が先頭要素から優先して行われていることが分かります。

take 5 で 5つの要素を取得しなければ、動き続けます。 take が欲しがる結果を優先して評価するように動作しています。

  • takeが欲しがる1つ目の結果は f x y の y を評価せずとも計算できます。
    • f 1 (traceMyFoldrLH f [] [..]) の部分で、 f 1 _ のように先頭要素の評価をします
    • (\x y -> (x * x) : y) の評価が行われ、 1 * 1 が評価されます。([1] と (traceMyFoldrLH f [] [2, 3, 4, ...]) とのリスト結合は後回し。)
  • takeが欲しがる2つ目の結果は、次のようになります。
    • f 1 (traceMyFoldrLH f [] [2, 3, 4, ...]) の (traceMyFoldrLH f [] [2, 3, 4, ...]) 部分を評価する
      • f 2 (traceMyFoldrLH f [] [..]) の部分で、 f 2 _ のように先頭要素の評価をします
      • (\x y -> (x * x) : y) の評価が行われ、 2 * 2 が評価されます。([4] と [3, 4, 5,..] とのリスト結合は後回し)

上記を続けることで、無限リストに対して期待通り動きます。

-- take 5 $ traceMyFoldrLH (\x y -> trace("(\x y -> (x * x) : y) = " ++ (show (x * x)) ++ ":y") $ (x * x) : y) [] ([1..] :: [Int])
traceMyFoldrLH f [] (1:[..]) = f 1 (traceMyFoldrLH f [] [..])
(\x y -> (x * x) : y) = 1:y
[1traceMyFoldrLH f [] (2:[..]) = f 2 (traceMyFoldrLH f [] [..])
(\x y -> (x * x) : y) = 4:y
,4traceMyFoldrLH f [] (3:[..]) = f 3 (traceMyFoldrLH f [] [..])
(\x y -> (x * x) : y) = 9:y
,9traceMyFoldrLH f [] (4:[..]) = f 4 (traceMyFoldrLH f [] [..])
(\x y -> (x * x) : y) = 16:y
,16traceMyFoldrLH f [] (5:[..]) = f 5 (traceMyFoldrLH f [] [..])
(\x y -> (x * x) : y) = 25:y
,25]
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?