F#版 Impureim Sandwichにした曲レコメンデーション
2025-05-19 17:30:25
原文: Song recommendations as an F# Impureim Sandwich by Mark Seemann
潜在的に膨大なデータに対する純粋関数
この記事は、連載記事「関数型プログラミングによる設計の代替アプローチ」の一部です。前回の記事「C#版 Impureim Sandwichにした曲レコメンデーション」では、Impureimサンドイッチパターンを、膨大な履歴データを処理する曲レコメンデーションエンジンの問題に適用する例を紹介しました。
Impureim Sandwichにした曲レコメンデーションでも述べた通り、Recawrサンドイッチの欠点（といえるかもしれません）は、純粋関数に渡す前に、すべてのデータを不純なソースから収集しなければならないことです。必要なデータがあまりに多すぎると、この戦略は現実的でなくなることがあります。今回のケースがこれに該当するかもしれませんが、我々人間にとって膨大に思えるデータも、コンピュータにとっては案外微々たるものというのは、よくあることです。
したがって、仮にこの例が現実的でないと感じたとしても、Recawrサンドイッチパターンをこの問題に適用する方法を示していきます。これは、前回のC#コードをF#に移植したものです。より現実的なアーキテクチャを見たい場合は、連載の最初の記事に戻って、目次から辿るとよいでしょう。
この記事では、Gitリポジトリの fsharp-pure-function ブランチを使用しています。
すべてのデータを収集する
前回の記事と同様に、SongService インターフェースに2つのメソッドを追加します。これにより、すべての曲とすべてのユーザーを列挙できるようになります。4つのメソッドを含む完全なインターフェースは次のようになります：
type SongService =
abstract GetAllSongs : unit -> Task<IEnumerable<Song>>
abstract GetAllUsers : unit -> Task<IEnumerable<User>>
abstract GetTopListenersAsync : songId : int -> Task<IReadOnlyCollection<User>>
abstract GetTopScrobblesAsync : userName : string -> Task<IReadOnlyCollection<Scrobble>>
記事「曲レコメンデーションのF#への移植」に示されたインターフェース定義と比較すると、GetAllSongs と GetAllUsers が新たに追加されたメソッドであることがわかります。
これらにより、すべてのトップリスナーおよびトップスクロブル（再生履歴）を収集できるようになりますが、これには時間がかかる場合があります。すべてのトップリスナーを集めるには、次の collectAllTopListeners アクションを追加することができます：
let collectAllTopListeners (songService : SongService) = task {
let d = Dictionary<int, IReadOnlyCollection<User>> ()
let! songs = songService.GetAllSongs ()
do! songs |> TaskSeq.iter (fun s -> task {
let! topListeners = songService.GetTopListenersAsync s.Id
d.Add (s.Id, topListeners) } )
return d :> IReadOnlyDictionary<_, _> }
同様に、すべてのトップスクロブルも次のようなアクションで集められます：
let collectAllTopScrobbles (songService : SongService) = task {
let d = Dictionary<string, IReadOnlyCollection<Scrobble>> ()
let! users = songService.GetAllUsers ()
do! users |> TaskSeq.iter (fun u -> task {
let! topScrobbles = songService.GetTopScrobblesAsync u.UserName
d.Add (u.UserName, topScrobbles) } )
return d :> IReadOnlyDictionary<_, _> }
お気づきかもしれませんが、これらは非常によく似ています。もし似たコードが3つ以上あったなら、共通部分を再利用可能な操作として抽出したくなったかもしれません。
どちらのケースでも、まず対象のリソース（曲やスクロブル）を列挙するためのアクションから始め、それぞれに対して「トップ」リソースを取得するアクションを呼び出します。ここには典型的な n+1 問題が存在しますが、それぞれのクエリは独立しているため、並列化することも考えられます。それでも、かなりの時間がかかり、場合によっては数時間かかることもあるでしょう。
すべてのデータはアクションごとに辞書に格納され、最後には2つの巨大な辞書が得られます。この2つのアクションが完了すれば、Recawrサンドイッチの read フェーズは完了です。
トラバーサル（Traversals）
先ほど出てきた TaskSeq.iter アクションについて疑問に思われたかもしれません。これは標準ライブラリの一部ではありません。それはいったい何で、どこから来たのでしょうか？
これは非同期のコマンドをより効率的にするために設計された、特殊なトラバーサルです。
let iter f xs = task {
let! units = traverse f xs
Seq.iter id units }
恒等関数（id）がなぜ有用なのか不思議に思ったことがあるなら、これがその一例です。最初の行では、units は unit のシーケンス（unit seq）です。TaskSeq.iter をできるだけ使いやすくするには、これら多数の unit を単一の unit に変換する必要があります。方法はいくつかありますが、私が思いつく中で最も簡潔なのが Seq.iter を使うことでした。Seq.iter は unit を返す関数を引数に取るため、すでに unit があるなら id 関数が適任です。
この iter アクションは TaskSeq モジュールの traverse 関数を使っています。この定義は次のようになっています：
let traverse f xs =
let go acc x = task {
let! x' = x
let! acc' = acc
return Seq.append acc' [x'] }
xs |> Seq.map f |> Seq.fold go (task { return [] })
traverse の型は ('a -> #Task<'c>) -> 'a seq -> Task<'c seq> です。つまり、シーケンスの 'a 型の値に対して非同期アクションを適用し、その結果として非同期ワークフロー Task<'c seq> を返します。
辞書のルックアップ
.NETでは、失敗する可能性のあるクエリは 慣習的に、out パラメータを取るメソッドでモデル化されます。辞書のルックアップにもこれが当てはまります。この種の設計は合成（composition）しにくいため、代わりに空の値を返す小さなヘルパー関数を追加すると便利です。一般的にはオプション値（option）を返すのが普通ですが、このケースでは空のコレクションの方が適切です。
let findOrEmpty key (d : IReadOnlyDictionary<_, IReadOnlyCollection<_>>) =
match d.TryGetValue key with
| true, v -> v
| _ -> List.empty
C#版でも同様のヘルパー関数を追加しており、そちらでは GetOrEmpty と呼んでいました。
ローカルな状態変更を伴う純粋関数
第一段階として、GetRecommendationsAsync メソッドを純粋関数に変換してみましょう。Gitリポジトリ内のコミットを見ればわかるように、実際にはマイクロコミットを重ねて変換しましたが、ここではもう少し大まかな変更の概要のみを示します。
クラスのメソッドではなく、引数として2つの辞書を取り、SongService への依存のない自己完結的な関数になっています。
let getRecommendations topScrobbles topListeners userName =
// 1. 自ユーザーのトップスクロブルを取得
// 2. 同じ曲を聴いた他ユーザーを取得
// 3. そのユーザーのトップスクロブルを取得
// 4. 曲を集約してレコメンドを生成
let scrobbles = topScrobbles |> Dict.findOrEmpty userName
let scrobblesSnapshot =
scrobbles
|> Seq.sortByDescending (fun s -> s.ScrobbleCount)
|> Seq.truncate 100
|> Seq.toList
let recommendationCandidates = ResizeArray ()
for scrobble in scrobblesSnapshot do
let otherListeners =
topListeners |> Dict.findOrEmpty scrobble.Song.Id
let otherListenersSnapshot =
otherListeners
|> Seq.filter (fun u -> u.TotalScrobbleCount >= 10_000)
|> Seq.sortByDescending (fun u -> u.TotalScrobbleCount)
|> Seq.truncate 20
|> Seq.toList
for otherListener in otherListenersSnapshot do
let otherScrobbles =
topScrobbles |> Dict.findOrEmpty otherListener.UserName
let otherScrobblesSnapshot =
otherScrobbles
|> Seq.filter (fun s -> s.Song.IsVerifiedArtist)
|> Seq.sortByDescending (fun s -> s.Song.Rating)
|> Seq.truncate 10
|> Seq.toList
otherScrobblesSnapshot
|> List.map (fun s -> s.Song)
|> recommendationCandidates.AddRange
let recommendations =
recommendationCandidates
|> Seq.sortByDescending (fun s -> s.Rating)
|> Seq.truncate 200
|> Seq.toList
:> IReadOnlyCollection<_>
recommendations
これは純粋関数なので、非同期ワークフローとして実行する必要がなくなりました。関数はもはや Task を返さず、Async サフィックスも省かれています。
ただし、実装にはまだ命令的な名残があります。空の ResizeArray（つまり List<T>）を初期化し、ネストされたループ内で何度も AddRange を呼び出しています。
関数にはローカルな状態の変更が含まれていますが、関数のスコープ外に漏れることはありません。この関数は同じ入力に対して常に同じ結果を返し、副作用もないので、参照透過性があります。
それでも「もっと関数型らしく」したいと思うかもしれませんね。それも実現可能です。
単一の式
式ベースの言語の興味深い特徴として、「1行のコード」で関数を記述することができる、というものがあります。もっとも、実際には横に非常に長くなりがちで、まったく読みにくく、保守が困難で、性能も悪くなることが多いため、常にそうしたいと思うものではありません。
しかし今回のケースでは、あえてそうすることも可能です。80x24 の制限に収めるために、複数行に分けて表現しています。
let getRecommendations topScrobbles topListeners userName =
// 1. 自ユーザーのトップスクロブルを取得
// 2. 同じ曲を聴いた他ユーザーを取得
// 3. そのユーザーのトップスクロブルを取得
// 4. 曲を集約してレコメンドを生成
topScrobbles
|> Dict.findOrEmpty userName
|> Seq.sortByDescending (fun s -> s.ScrobbleCount)
|> Seq.truncate 100
|> Seq.collect (fun scrobble ->
topListeners
|> Dict.findOrEmpty scrobble.Song.Id
|> Seq.filter (fun u -> u.TotalScrobbleCount >= 10_000)
|> Seq.sortByDescending (fun u -> u.TotalScrobbleCount)
|> Seq.truncate 20
|> Seq.collect (fun otherListener ->
topScrobbles
|> Dict.findOrEmpty otherListener.UserName
|> Seq.filter (fun s -> s.Song.IsVerifiedArtist)
|> Seq.sortByDescending (fun s -> s.Song.Rating)
|> Seq.truncate 10
|> Seq.map (fun s -> s.Song)))
|> Seq.sortByDescending (fun s -> s.Rating)
|> Seq.truncate 200
|> Seq.toList
:> IReadOnlyCollection<_>
正直に言えば、コメント4行を含めると関数定義は24行を超えてしまいますが、コメントがなければ、この書き方は実際に 80x24 の枠に収まります。とはいえ、これがこの関数を整理し、配置する最善の方法だと主張するつもりはありません。
「密度が高すぎる」「矢印コードのようで不安だ」と感じるかもしれません。
私も異論はありませんが、少なくともこのバージョンは、関数が参照透過であるだけでなく、ローカルな状態変更を使わずに実装されているというマイルストーンには達しています。それが最も重要な基準というわけではありませんが、完全に式ベースで実装されていれば、より小さな構成要素に分割するのも簡単になります。
より小さな関数からの合成
可読性と保守性を向上させるため、今度はヘルパー関数を抽出していきます。最初の対象はすぐに思いつきます。
let private getUsersOwnTopScrobbles topScrobbles userName =
topScrobbles
|> Dict.findOrEmpty userName
|> Seq.sortByDescending (fun s -> s.ScrobbleCount)
|> Seq.truncate 100
上記コードリストに含まれる各サブ式も同様に、ヘルパー関数として抽出する候補になります。例えば、以下のような形です：
let private getOtherUsersWhoListenedToTheSameSongs topListeners scrobble =
topListeners
|> Dict.findOrEmpty scrobble.Song.Id
|> Seq.filter (fun u -> u.TotalScrobbleCount >= 10_000)
|> Seq.sortByDescending (fun u -> u.TotalScrobbleCount)
|> Seq.truncate 20
これらのヘルパー関数は private としてマークされており、getRecommendations 関数をエクスポートするモジュールの内部実装にとどまるようになっています。
さらにいくつかのヘルパー関数を用意すれば、以下のようにそれらを組み合わせて getRecommendations 関数を実装できるようになります。
let getRecommendations topScrobbles topListeners =
getUsersOwnTopScrobbles topScrobbles
>> Seq.collect (
getOtherUsersWhoListenedToTheSameSongs topListeners
>> Seq.collect (getTopSongsOfOtherUser topScrobbles))
>> aggregateSongsIntoRecommendations
ここで、各ヘルパー関数の名前は、以前のバージョンで使っていたコードコメントに由来しています。「コードコメントは、コードをうまく構成できなかったことの謝罪だ」とする考え方にならえば、今回の構造ではそうした謝罪は不要になったということです。
結論
必要なデータを永続データ構造に収められるという（やや突飛な）前提を受け入れられるのであれば、レコメンデーションアルゴリズムを純粋関数へリファクタリングするのは、それほど難しくありません。これがRecawrサンドイッチの「純粋な」部分です。ここでは実際のサンドイッチ構造そのものは示していませんが、C#版 Impureim Sandwichと同一です。
今回示したコードの最終形は、個人的にはとても魅力的だと感じています。ヘルパー関数は private に保っていますが、必要であれば public に昇格させることもできます。それはコード全体のテストのしやすさを高める可能性がありますが、その一方でAPIの表面積が広がり、メンテナンスやセキュリティ上の負担が増すリスクもあります。
トレードオフは常に考慮すべきです。この例では、最終的に入力データが大きすぎてこのアプローチが現実的でないと判断する可能性もありますが、私の経験では、この種のアーキテクチャが有効に働くケースは他にもたくさんあります。たとえ入力サイズが数十MB程度あったとしても、Impureimサンドイッチがもたらす設計の簡素化は、メモリ使用量の増加を補って余りあるかもしれません。性能が気になるなら、計測しましょう。
次回は、別のアーキテクチャを検討する前に、このバリエーションがHaskellでどのようになるかを見ていきます。本連載の方針として、Haskellに興味がない場合は、連載の最初の記事の目次に戻り、興味のある別の記事に進んでも構いません。
次回： Haskell版 Impureim Sandwichにした曲レコメンデーション