[Haskell] f <$> x <*> y よりも liftA2 f x y の方が計算コストを抑えられることがある

`Applicative` の値に関数を適用したいとき、`liftA2` 関数を用いると演算子 `<$>` を使用するより計算コストを抑えられることがあります。

意味的には `liftA2 f x y = f <$> x <*> y` です (※定義ではなく、実際の計算方法は異なります) 。

参考「[liftA2 - Control.Applicative](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Applicative.html#v:liftA2)」

参考「[[Haskell] モナド 演算子 まとめ - Qiita](https://qiita.com/kerupani129/items/333155e5e2dee644d6dc)」

# 1. `liftA2` 関数および `liftA3` 関数

ここでは説明のため各演算子および関数の型クラス制約を略しますが、型変数 `f` の型は `Functor` および `Applicative` クラスのインスタンスです。

`liftA2` 関数および `liftA3` 関数の型は以下のようになっています。

```haskell
-- Functor (比較用)
(<$>)  :: (a  -> b            ) -> f a  -> f b

-- Applicative
liftA2 :: (a  -> b  -> c      ) -> f a  -> f b  -> f c
liftA3 :: (a  -> b  -> c  -> d) -> f a  -> f b  -> f c  -> f d
```

`liftA3` 関数の定義は以下のようになっています。

※説明のためソースコードを一部改変。

```haskell
liftA3 f x y z = liftA2 f x y <*> z
```

参考「[liftA3 - Control.Applicative](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Applicative.html#v:liftA3)」

## 1.1. 使い方

インスタンス `Applicative f` に関して、`liftA2` 関数は `a  -> b  -> c` 型の関数から `f a -> f b -> f c` 型の関数へ変換します。

`liftA3` 関数は `a  -> b  -> c -> d` 型の関数から `f a -> f b -> f c - f d` 型の関数へ変換します。

さらに引数が多い場合は演算子 `<*>` を用います。

```haskell
import Control.Applicative (liftA2, liftA3)

f :: Int -> Int -> Int
f = (+)

g :: Int -> Int -> Int -> Int
g x y z = x + y + z

h :: Int -> Int -> Int -> Int -> Int
h x y z w = x + y + z + w

main :: IO ()
main = do

    let x = Just 10 :: Maybe Int
    let y = Just 20 :: Maybe Int
    let z = Just 30 :: Maybe Int
    let w = Just 40 :: Maybe Int

    -- 
    print (f <$> x <*> y :: Maybe Int)

    print (liftA2 f x y  :: Maybe Int)

    -- 
    print (g <$> x <*> y <*> z :: Maybe Int)

    print (liftA3 g x y z      :: Maybe Int)
    print (liftA2 g x y <*> z  :: Maybe Int)

    -- 
    print (h <$> x <*> y <*> z <*> w :: Maybe Int)

    print (liftA3 h x y z <*> w      :: Maybe Int)
    print (liftA2 h x y <*> z <*> w  :: Maybe Int)
```

## 1.2. 計算コスト

### 1.2.1. `Maybe` 型の場合

`Maybe` 型における演算子 `<$>` および `<*>` の定義は以下のようになっています。

※説明のためソースコードを一部改変。

```haskell
fmap _ Nothing  = Nothing
fmap f (Just x) = Just (f x)

(<$>) = fmap
```

```haskell
Just f  <*> x = fmap f x
Nothing <*> _ = Nothing
```

よって、`Maybe` 型における `f <$> x <*> y`  は以下のような計算を行います:

1. 値 `x` が `Just` か `Nothing` か判断して関数 `f` を適用する
1. 関数 `f <$> x` が `Just` か `Nothing` か判断して値 `y` に適用する
1. 値 `y` が `Just` か `Nothing` か判断して関数 `f <$> x` を適用する

一方で、`Maybe` 型における `liftA2` 関数の定義は以下のようになっています。

```haskell
liftA2 f (Just x) (Just y) = Just (f x y)
liftA2 _ _ _ = Nothing
```

よって、`Maybe` 型における `liftA2 f x y`  は以下のような計算を行います:

1. `x` が `Just` か `Nothing` か判断して関数 `f` を適用する
1. `y` が `Just` か `Nothing` か判断して関数 `liftA2 f x` を適用する

上記のことから `f <$> x <*> y` より `liftA2 f x y` の方が計算量が減っていることが分かります。

参考「[Maybe - Data.Maybe](https://hackage.haskell.org/package/base-4.19.0.0/docs/Data-Maybe.html#t:Maybe)」

### 1.2.2. `ZipList` 型の場合

`ZipList` 型における演算子 `<$>` および `<*>` の定義は以下のようになっています。

※説明のためソースコードを一部改変。

```haskell
-- List
fmap = map

-- ZipList
newtype ZipList a = ZipList { getZipList :: [a] }
    deriving Functor

fmap f (ZipList xs) = ZipList (fmap f xs)

(<$>) = fmap
```

```haskell
id x = x

-- List
zipWith f = go
  where
    go [] _ = []
    go _ [] = []
    go (x:xs) (y:ys) = f x y : go xs ys

-- ZipList
liftA2 f (ZipList xs) (ZipList ys) = ZipList (zipWith f xs ys)

(<*>) = liftA2 id
```

演算子 `<*>` の定義を整理すると以下のようになります。

```haskell
id x = x

-- List
zipWith f = go
  where
    go [] _ = []
    go _ [] = []
    go (x:xs) (y:ys) = f x y : go xs ys

-- ZipList
(<*>) (ZipList fs) (ZipList xs) = ZipList (zipWith id fs xs)
```

参考「[6.6.4.1. Deriving Functor instances - 6.6.4. Deriving instances of extra classes (Data, etc.) — Glasgow Haskell Compiler @ProjectVersion@ User's Guide](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/deriving_extra.html#deriving-functor-instances)」

よって、`ZipList` 型における `f <$> xs <*> ys`  は以下のような計算を行います:

1. `xs` の各要素の値に関数 `f` を適用する
1. `ys` の各要素の値に `f <$> xs` の各要素の関数を適用する

一方で、`ZipList` 型における `liftA2` 関数の定義は以下のようになっています。

```haskell
id x = x

-- List
zipWith f = go
  where
    go [] _ = []
    go _ [] = []
    go (x:xs) (y:ys) = f x y : go xs ys

-- ZipList
liftA2 f (ZipList xs) (ZipList ys) = ZipList (zipWith f xs ys)
```

よって、`ZipList` 型における `liftA2 f xs ys`  は以下のような計算を行います:

1. `xs` と `ys` それぞれの各要素の値に関数 `f` を適用する

上記のことから `f <$> xs <*> ys` より `liftA2 f xs ys` の方が計算量が減っていることが分かります。

参考「[ZipList - Control.Applicative](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Applicative.html#t:ZipList)」

# 2．`liftM2` 関数等

`liftM2` 関数は `liftA2` 関数と計算結果が同じになりますが、実際の計算方法は異なります。

インスタンス `Monad m` に関して、`liftM2` 関数は `a  -> b  -> c` 型の関数から `m a -> m b -> m c` 型の関数へ変換します。

※ `liftM3`, `liftM4` および `liftM5` 関数も同様。

参考「[Monadic lifting operators - Control.Monad](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Monad.html#g:7)」

## 2.1. `liftM2` 関数の定義

`liftM2` 関数の定義は以下のようになっています。

※説明のためソースコードを一部改変。

```haskell
liftM2 f x y = do
    x' <- x
    y' <- y
    pure $ f x' y'
```

`liftM2` 関数の定義を整理すると以下のようになります。

```haskell
liftM2 f x y = x >>= \x' -> y >>= \y' -> pure $ f x' y'
```

## 2.2. 計算コスト

`Maybe` 型における演算子 `>>=` の定義は以下のようになっています。

※説明のためソースコードを一部改変。

```haskell
(Just x) >>= f = f x
Nothing  >>= _ = Nothing
```

よって、`Maybe` 型における `liftM2` 関数は以下のような計算を行います:

1. 値 `x` に関数 `\x' -> y >>= \y' -> pure $ f x' y'` を適用する
1. 値 `y` に関数 `\y' -> pure $ f x' y'` を適用する

上記のことから `f <$> x <*> y` より `liftM2 f x y` の方が計算量が減る可能性はありますが、`liftA2` 関数のように各インスタンスごとに定義されるものではないため、計算コストが重要であれば `liftM2` 関数でなく `liftA2` 関数を使用します。

計算コストを気にしない、または十分な場合に `liftA2 = liftM2` のように `liftA2` 関数の定義に用いられることがあります。

参考「[Maybe - Data.Maybe](https://hackage.haskell.org/package/base-4.19.0.0/docs/Data-Maybe.html#t:Maybe)」
参考「[liftM2 - Control.Monad](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Monad.html#v:liftM2)」

# 3. `liftA` 関数および `liftM` 関数

`liftA` 関数および `liftM` 関数は `(<$>) = fmap` と同じ意味です。

`fmap` 関数は `Functor` のインスタンスごとに最適な定義がされているはずのため、`liftA` 関数および `liftM` 関数は不要です。

`fmap = liftA` のように `fmap` 関数の定義に用いられることがあります。

参考「[liftA - Control.Applicative](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Applicative.html#v:liftA)」
参考「[liftM - Control.Monad](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Monad.html#v:liftM)」

# 4. `ap` 関数

`ap` 関数は `(<*>)` と同じ意味です。

演算子 `<*>` は `Applicative` のインスタンスごとに最適な定義がされているはずのため、`ap` 関数は不要です。

`(<*>) = ap` のように演算子 `<*>` の定義に用いられることがあります。

参考「[ap - Control.Monad](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Monad.html#v:ap)」

# 5. まとめ

モナドの値に関数を適用できるように変換する関数は以下のようなものがありますが、重要なのは `liftA2` 関数です:

- `Applicative`
    - `liftA`, `liftA2`, `liftA3`
- `Monad`
    - `liftM`, `liftM2`, `liftM3`, `liftM4`, `liftM5`
    - `ap`