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

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

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

参考「liftA2 - Control.Applicative」

参考「[Haskell] モナド 演算子 まとめ - Qiita」

1. liftA2 関数および liftA3 関数

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

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

-- 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 関数の定義は以下のようになっています。

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

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

参考「liftA3 - Control.Applicative」

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 型の関数へ変換します。

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

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 型における演算子 <$> および <*> の定義は以下のようになっています。

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

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

(<$>) = fmap

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

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

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

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

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

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

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

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

参考「Maybe - Data.Maybe」

1.2.2. ZipList 型の場合

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

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

-- List
fmap = map

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

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

(<$>) = fmap

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

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

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」

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

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

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

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」

2．liftM2 関数等

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

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

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

参考「Monadic lifting operators - Control.Monad」

2.1. liftM2 関数の定義

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

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

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

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

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

2.2. 計算コスト

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

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

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

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

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

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

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

参考「Maybe - Data.Maybe」
参考「liftM2 - Control.Monad」

3. liftA 関数および liftM 関数

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

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

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

参考「liftA - Control.Applicative」
参考「liftM - Control.Monad」

4. ap 関数

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

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

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

参考「ap - Control.Monad」

5. まとめ

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

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