# traverse 再入門
- [The programmer that controls the `traverse`, controls the code.](https://gakuzzzz.github.io/slides/controls_the_traverse_controls_the_code/#1)
- [map を使いこなせるあなたに traverse](https://zenn.dev/gakuzzzz/articles/81cd723a36067f)
をきっかけにいまいち使いこなせていない `traverse` に再入門する。
がくぞさんのは Scala の話だが、Haskell にももちろん `traverse` がある。
----
# traverse
`traverse` は
- アプリカティブファンクターの文脈を考慮しながら、リストの各要素に関数を適用するための関数
- より抽象的には「構造を保ったまま要素に関数を適用する」関数
```haskell
traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)
```
### 具体例
```haskell
import Data.Char (digitToInt)
main :: IO ()
main = do
print $ traverse Just [1, 2, 3] -- Just [1, 2, 3]
print $ traverse (safeDiv 10) [1, 2, 5, 0] -- Nothing
-- アプリカティブファンクター
-- 文脈付きの値を返す (この場合はMaybe)
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)
```
このように、`traverse`はリストの各要素に関数を適用しつつ、アプリカティブファンクターの文脈を考慮した処理ができる
**アプリカティブファンクター** は、ここでは計算結果が文脈をもつ関数だと思えば良い
- アプリカティブファンクター: 文脈付きで値を返すような計算。`safeDiv`のように、入力自体はコンテナに包まれていないが、出力がコンテナに包まれる（典型的には`Maybe`で失敗を表すなど）。
- `traverse`: そういうアプリカティブファンクターをリストに適用したときに、単にリストのそれぞれにそのアプリカティブファンクターを適用するだけでなく、リストが全体としてどういう文脈になったかまでを評価してくれる。
`traverse`は、リストの要素に対してアプリカティブファンクターを適用しつつ、リスト全体の文脈も考慮してくれる。例えば、`Maybe`を使ったエラー処理や、`[]`（リスト）を使った非決定性計算など、アプリカティブファンクターを使ったさまざまな計算を効率的に行うことができる。
## sequenceA は traverse の特殊ケース
`sequenceA` は `traverse` の特殊なケース。
`sequenceA` はアプリカティブファンクターのリストを受け取り、そのリストの要素を逆にアプリかティブファンクターに詰め込む。
```haskell
sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)
```
`traverse` と `sequenceA` の関係は以下のようになる
```haskell
sequenceA = traverse id
```
### 具体例
```haskell
main = do
print $ sequenceA [Just 10, Just 20, Just 30] -- Just [10, 20, 30]
print $ sequenceA [Just 10, Just 20, Just 30, Nothing] -- Nothing
```
----
# traverse の利用例
## Maybe で Fail Fast
```haskell
import Data.Char (digitToInt)
main :: IO ()
main = do
print $ traverse Just [1, 2, 3] -- Just [1, 2, 3]
print $ traverse (safeDiv 10) [1, 2, 5, 0] -- Nothing
-- アプリカティブファンクター
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)
```
結果が失敗するかもしれない関数をリストに適用したいとき。
## readMaybe
```haskell
import Text.Read (readMaybe)
main :: IO ()
main = do
let input1 = ["1", "2", "three", "4"]
print (traverse readMaybe input1 :: Maybe [Int]) -- Nothing
let input2 = ["1", "2", "4"]
print (traverse readMaybe input2 :: Maybe [Int]) -- Just [1, 2, 4]
```
先の例のさらに具体的なケース。入力の検査。
`readMaybe` は `Maybe` アプリカティブファンクターを返す。入力の検証が失敗すると `Nothing` が返され、全てが正しく検証されると `Just` が返る
neverthrow の `Reuslt.combine` そのもの
## Either との組み合わせ
Maybe は Either の特殊ケース (と、せつラボ本にも書いてあった) なので、当然 Either との組み合わせは Maybe のとき同様の構造になる
```haskell
import Text.Read (readMaybe)
readEither :: Read a => String -> Either String a
readEither s = case readMaybe s of
Just x -> Right x
Nothing -> Left $ "Could not parse: " ++ s
main :: IO ()
main = do
-- Either と組み合わせる
let input = ["1", "2", "three", "4", "five"]
print (traverse readEither input :: Either String [Int]) -- Left "Could not parse: three"
```
なお、がくぞさんの資料にある Scala の Validation でエラーを集約したいケースは Haskell なら either パッケージにある Data.Validation を使うといいようだ。(残念ながら、標準ライブラリではない)
## 非決定計算
```haskell
{-# OPTIONS_GHC -Wno-type-defaults #-}
main :: IO ()
main = do
let xs = [1, 2]
print $ traverse (\x -> [x - 1, x + 1]) xs -- [[0,1],[0,3],[2,1],[2,3]]
```
入力のリストに対して複数の関数を適用した組み合わせを返す。
これは競技プログラミングでもよくあるような例に思う。強力な計算という意味ではやはり非決定計算にうまく使いたい。
### sequenceA + リストのリスト
3つの集合があったとき、それぞれから1つずつ選ぶ全ての組み合わせを生成する
```haskell
main :: IO ()
main = do
let input = [[1, 2], [3, 4], [5, 6]]
print $ sequenceA input -- [[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
```
まあでもこれは `sequence` を使う場合と一緒
## IO
```haskell
import Control.Monad (forM)
main :: IO ()
main = do
let files = ["file1.txt", "file2.txt", "file3.txt"]
contents <- traverse readFile files
forM contents putStrLn
```
複数のファイルを一度に読み込むとか。
---
# Traversable クラス (※過去にメモっていた)
traverse は、データ構造の中の各要素に関数を適用する様式を一般化したもの。
```haskell
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
```
例えばこれを `f` が失敗するかもしれないと仮定してみる。
すなわち関数 `f` の型は `a -> b` ではなく `a -> Maybe b` となる
```haskell
traverse :: (a -> Maybe b) -> [a] -> Maybe [b]
traverse f [] = pure []
traverse f (x:xs) = pure (:) <*> f x <*> traverse f xs
```
全体が成功するのはすべての関数適用が成功するときだけ、とする
すべてが成功すると `Just [1, 2, 3]` のような値が返るし、失敗すると `Nothing` が返る
```haskell
dec :: Int -> Maybe Int
dec n
| n > 0 = Just (n - 1)
| otherwise = Nothing
main :: IO ()
main = do
print $ traverse dec [1, 2, 3] -- Just [1, 2, 3]
print $ traverse dec [0, 2, 3] -- Nothing
```
実際の `traverse` は以下のように定義されている
```haskell
*Main Data.Foldable Data.Monoid> :type traverse
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
```
- `Traversable` なコンテナに入っている
- 関数の文脈は `Applicative` である
リストは Traversalbe なコンテナであり、Maybe は Applicative である
**「関数の結果に作用があると map は使えないな･･･」と思いがちなところ、そこで `traverse` ですよ !**
----
# foldM
`traverse` は `map` の一般化で、mapping 写像にアプリカティブファンクターを適用することができるのは、ここまで見た通り。
ところで、写像ではなく畳み込みでもアプリカティブファンクターを使いたい時がある。
そういう時は、`foldl` のモナド一般化である `foldM` を使う。
```haskell
import Control.Monad (foldM)
main :: IO ()
main = do
-- foldM は foldl の一般化
print $ foldM safeDiv 12 [2, 4, 6] -- Just 0
print $ foldM safeDiv 12 [2, 0, 6] -- Nothing
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)
```
`foldM` を使えばアプリカティブファンクターの入力の型を変えるとかコンテナから値を取り出すとかしなくてもそのまま畳み込み関数が可能。結果は当然合成される。
## 競技プログラミングでの事例
[B - Multiplication 2](https://atcoder.jp/contests/abc169/tasks/abc169_b)
入力で与えられた整数を掛け算で畳み込むが $10^{18}$ を超えたら `-1` を出力するという問題。
```
3
101 9901 999999000001
```
これは
```
-1
```
と出力するのが正しい。
再帰や `iterate` なんかでアキュムレータが $10^{18}$ を超えたら計算を打ち切る...というのがすぐに思い浮かぶが「掛け算が失敗したら `Nothing` を返す」というアプリカティブファンクターを適用するようにすると、より宣言的に記述できる。
```haskell
import Control.Monad (foldM)
import qualified Data.ByteString.Char8 as BS
import Data.Char (isSpace)
import Data.List (unfoldr)
import Data.Maybe (fromMaybe)
getInts :: IO [Int]
getInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <
gt; BS.getLine
f :: Int -> Int -> Maybe Int
f acc a
| acc <= 10 ^ (18 :: Int) `div` a = Just (acc * a)
| otherwise = Nothing
main :: IO ()
main = do
_ <- getLine
as <- getInts
print $
if 0 `elem` as
then 0
else fromMaybe (- 1) (foldM f 1 as)
```
なお、オーバーフローを考慮して掛け算ではなく割り算にしてチェックしている。
- `map` の一般化 (`Applicative`) ··· `traverse`
- `map` の一般化 (`Monad`) ··· `mapM`
- `foldl` の一般化 (`Monad`) ··· `foldM`
という関係になっている。
アプリカティブファンクターを適用する、という文脈で `mapM` や `foldM` を捉え直すと、使いたい場面に紐付けやすい気がした。