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

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

### 環境

* GHC 8.4.4 (Ubuntu 18.04 LTS)

## Input と Output

**入力**

```haskell
[1..]
```

**出力**

```haskell
[1,4,9,16,25]
```


## リスト内包表記

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

```haskell
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` 決め打ちになってしまいます。)

```haskell
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` はリスト専用ですね。

```haskell
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` の別名の中置演算子 `<$>` が用意されていて、同じように結果を出力できます。

```haskell
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つだけ指定しています。

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

## Monad

```haskell
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

```haskell
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` の評価が優先されます。

```haskell
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])
```

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

```haskell
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` 自体は後ろの要素から評価するコードなので、 **ある意味見かけ上のコード通りの評価順** ではあります。

```haskell
-- 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 の内容を文字列化するのをやめました。

```haskell
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,..]` とのリスト結合は後回し)

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

```haskell
-- 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]
```