Haskell版 Impureim Sandwichにした曲レコメンデーション
2025-05-30 03:00:25
原文: Song recommendations as a Haskell Impureim Sandwich by Mark Seemann
潜在的に膨大なデータに対する純粋関数。
この記事は、関数型プログラミングによる設計の代替アプローチという記事シリーズの一部です。タイトルが示す通り、このシリーズでは、関数型プログラミングの原則を特定の課題に適用するさまざまな方法について取り上げています。すべての記事で同じ課題に取り組んでおり、簡単に言うと、「膨大なデータセットに基づいて、ユーザー向けの曲レコメンデーションを算出する」ことが課題です。シリーズの前半では、この課題の詳細な説明を行っています。
前回の記事では、F# の「ベースコード」を純粋関数へとリファクタリングする方法を見ました。今回の記事では、Haskell に移植された曲レコメンデーションの「ベースコード」に対して同様のリファクタリングを行います。
この記事で取り上げる Git ブランチは、Haskell リポジトリの pure-function ブランチです。
データの収集
前回までの記事と同様に、まず SongService 型クラスに 2 つのメソッドを追加し、全ての曲と全ユーザーを列挙できるようにします。4 つのメソッドを持つ完全な型クラスは次のようになります：
class SongService a where
getAllSongs :: a -> IO [Song]
getAllUsers :: a -> IO [User]
getTopListeners :: a -> Int -> IO [User]
getTopScrobbles :: a -> String -> IO [Scrobble]
曲レコメンデーションのHaskellへの移植で示した型クラス定義と比較すると、getAllSongs と getAllUsers が新たに追加されたメソッドであることがわかります。
これらによって、全トップリスナーと全トップスクロブル（再生履歴）を収集できます。時間はかかりますが可能です。全トップリスナーを収集するには、以下のような collectAllTopListeners アクションを追加します：
collectAllTopListeners srvc = do
songs <- getAllSongs srvc
listeners <- newIORef Map.empty
forM_ songs $ \song -> do
topListeners <- getTopListeners srvc $ songId song
modifyIORef listeners (Map.insert (songId song) topListeners)
readIORef listeners
同様に、全トップスクロブルも次のようなアクションで集約できます：
collectAllTopScrobbles srvc = do
users <- getAllUsers srvc
scrobbles <- newIORef Map.empty
forM_ users $ \user -> do
topScrobbles <- getTopScrobbles srvc $ userName user
modifyIORef scrobbles (Map.insert (userName user) topScrobbles)
readIORef scrobbles
お気づきかもしれませんが、2 つのアクションは非常に似ています。もし似たコードが3つ以上あったなら、共通部分を抽出して再利用できる操作として切り出したくなるほどです。
いずれの場合も、まず対象リソース（曲またはスクロブル）を列挙できるアクションを使い、それぞれに対して「トップ」リソースを取得するアクションを呼び出します。ここには典型的な n+1 問題がありますが、各クエリは独立しているため並列化も可能です。それでも、多くの時間がかかることは避けられず、場合によっては数時間単位になります。
なぜこれらのアクションでよりイディオマティックな合成ベースの表現ではなく、IORef を使っているのか疑問に思うかもしれません。実際、普段なら私もそうするところですが、今回は IO 処理に大きく依存していること、そして Haskell のコードを F# のコードと近づけることを意図しました。普段であれば重視しませんが、今回に限ってはコードベースを比較しやすくなると考えたからです。
各アクションは Map に格納され、結果として 2 つの大規模なマップが得られます。これらのアクションが完了すれば、Recawr サンドイッチにおける read フェーズは完了です。
ローカルなミューテーションを用いた参照透過関数
最初のステップとして、getRecommendations アクションを参照透過な関数に変換したくなります。Git リポジトリのコミット履歴を見ると、実際には マイクロコミットを重ねてこの変更を行ったのがわかりますが、ここではそれを大まかにまとめた形で紹介します。
このバージョンでは srvc（SongService）パラメータを削除し、代わりに topScrobbles と topListeners の 2 つのマップを引数として受け取るようにしました。
getRecommendations :: Map String [Scrobble] -> Map Int [User] -> String -> IO [Song]
getRecommendations topScrobbles topListeners un = do
-- 1. 自ユーザーのトップスクロブルを取得
-- 2. 同じ曲を聴いた他ユーザーを取得
-- 3. そのユーザーのトップスクロブルを取得
-- 4. 曲を集約してレコメンドを生成
let scrobbles = Map.findWithDefault [] un topScrobbles
let scrobblesSnapshot = take 100 $ sortOn (Down . scrobbleCount) scrobbles
recommendationCandidates <- newIORef []
forM_ scrobblesSnapshot $ \scrobble -> do
let otherListeners =
Map.findWithDefault [] (songId $ scrobbledSong scrobble) topListeners
let otherListenersSnapshot =
take 20 $
sortOn (Down . userScrobbleCount) $
filter ((10_000 <=) . userScrobbleCount) otherListeners
forM_ otherListenersSnapshot $ \otherListener -> do
let otherScrobbles =
Map.findWithDefault [] (userName otherListener) topScrobbles
let otherScrobblesSnapshot =
take 10 $
sortOn (Down . songRating . scrobbledSong) $
filter (songHasVerifiedArtist . scrobbledSong) otherScrobbles
forM_ otherScrobblesSnapshot $ \otherScrobble -> do
let song = scrobbledSong otherScrobble
modifyIORef recommendationCandidates (song :)
recommendations <- readIORef recommendationCandidates
return $ take 200 $ sortOn (Down . songRating) recommendations
IO [Song] を返すため、一見まだ不純なように見えますが、完全に決定論的で副作用がないため参照透過性は保たれています。
このリファクタリングの順序は、私にとって意味のあるものでした。SongService パラメータの除去のほうが、IO ラッパーの除去よりも重要だったのです。
とはいえ、これはよりイディオマティックな純粋関数に向けた中間段階にすぎません。
単一の式
式ベースの言語に特有の性質として、関数を「1 行」で書くことが可能です。もちろん、それは横に非常に長く読みにくく、保守も困難でパフォーマンスも悪くなりがちなので、常にそうすべきとは限りません。
とはいえ、このケースでは「1 行関数」は実現可能です。ただし、80×24 の制約を守るために複数行に分割しています。
getRecommendations :: Map String [Scrobble] -> Map Int [User] -> String -> [Song]
getRecommendations topScrobbles topListeners un =
-- 1. 自ユーザーのトップスクロブルを取得
-- 2. 同じ曲を聴いた他ユーザーを取得
-- 3. そのユーザーのトップスクロブルを取得
-- 4. 曲を集約してレコメンドを生成
take 200 $
sortOn (Down . songRating) $
fmap scrobbledSong $
(\otherListener -> take 10 $
sortOn (Down . songRating . scrobbledSong) $
filter (songHasVerifiedArtist . scrobbledSong) $
Map.findWithDefault [] (userName otherListener) topScrobbles) =<<
(\scrobble -> take 20 $
sortOn (Down . userScrobbleCount) $
filter ((10_000 <=) . userScrobbleCount) $
Map.findWithDefault [] (songId $ scrobbledSong scrobble) topListeners) =<<
take 100
(sortOn (Down . scrobbleCount) $ Map.findWithDefault [] un topScrobbles)
このスナップショットでは IORef と IO を完全に排除しました。関数は依然として参照透過であり、Haskell 自身もそれを認識できるようになりました。
それでも、このコードは密集していて分かりづらいですね。Haskell は通常、右から左、そして下から上に読むというのも助けになりません。この関数の可読性を改善する方法はあるでしょうか？
小さな関数からの合成
可読性と保守性を向上させるため、ヘルパー関数を抽出していきましょう。まず最初の例は自然に導き出せます。
getUsersOwnTopScrobbles :: Ord k => Map k [Scrobble] -> k -> [Scrobble]
getUsersOwnTopScrobbles topScrobbles un =
take 100 $
sortOn (Down . scrobbleCount) $ Map.findWithDefault [] un topScrobbles
このコードに登場する各サブ式は、同様にヘルパー関数へと分離可能です。例えば次のように：
getOtherUsersWhoListenedToTheSameSongs :: Map Int [User] -> Scrobble -> [User]
getOtherUsersWhoListenedToTheSameSongs topListeners scrobble =
take 20 $
sortOn (Down . userScrobbleCount) $
filter ((10_000 <=) . userScrobbleCount) $
Map.findWithDefault [] (songId $ scrobbledSong scrobble) topListeners
コードリストからは分かりませんが、これらの関数はモジュール外に公開されていません。あくまで実装の詳細として留まっています。
さらにいくつかのヘルパー関数を用意すれば、getRecommendations 関数をそれらの合成で実装できます。
getRecommendations :: Map String [Scrobble] -> Map Int [User] -> String -> [Song]
getRecommendations topScrobbles topListeners un =
-- 1. 自ユーザーのトップスクロブルを取得
-- 2. 同じ曲を聴いた他ユーザーを取得
-- 3. そのユーザーのトップスクロブルを取得
-- 4. 曲を集約してレコメンドを生成
aggregateSongsIntoRecommendations $
getTopSongsOfOtherUser topScrobbles =<<
getOtherUsersWhoListenedToTheSameSongs topListeners =<<
getUsersOwnTopScrobbles topScrobbles un
Haskell は右から左に関数を合成するため、複数行に分割する場合（80×24 の制約を考慮して）、下から上に読む必要があります。
この状況は、Data.Function から & 演算子をインポートすれば改善できます：
getRecommendations :: Map String [Scrobble] -> Map Int [User] -> String -> [Song]
getRecommendations topScrobbles topListeners un =
getUsersOwnTopScrobbles topScrobbles un >>=
getOtherUsersWhoListenedToTheSameSongs topListeners >>=
getTopSongsOfOtherUser topScrobbles &
aggregateSongsIntoRecommendations
ヘルパー関数には、前のバージョンのコードに添えられていたコメントをもとに名前をつけています。コメントとは、コードを適切に構造化できていないことへの謝罪だとすれば、今やそれは不要になったというわけです。
結論
膨大なデータを 永続データ構造 に格納できるという（多少無茶な）仮定を受け入れられるのであれば、レコメンデーションのアルゴリズムを純粋関数へとリファクタリングするのはそれほど難しくありません。これが Recawr サンドイッチにおける「純粋」部分です。実際のサンドイッチ構造自体はここでは示していませんが、非常に単純で、Haskell リポジトリのテストに含まれています。また、データ収集処理をすべてアプリケーションの境界に移せば、SongService 型クラス自体が不要になる可能性もあります。
今回紹介したコードの最終形は、私としては非常に好ましく思います。ヘルパー関数はモジュール内に留めていますが、必要に応じて公開することもできます。これは、コードベース全体のテスト容易性を高める可能性がある一方で、API の表面積が広がるという代償も伴います。
トレードオフは常に存在します。この例では、入力データが大きすぎてこの手法が実用的でないと思えるかもしれませんが、私の経験ではこのようなアーキテクチャが適しているケースは数多く存在します。入力サイズが数十メガバイト程度であれば、Impureim サンドイッチがもたらす簡素さは、メモリフットプリントの増大を上回る利点になるかもしれません。いつでもそうですが、パフォーマンスが気になるなら、測定すべきです。
この記事で、Recawr サンドイッチによる解法の概要は終了です。TB（テラバイト）単位、あるいはそれ以上のメモリを使用するプログラムを実行するというのは現実的とは言い難いため、次回は別のアーキテクチャに目を向けていきます。