曲レコメンデーションのHaskellへの移植
2025-04-22 08:30:25
原文: Porting song recommendations to Haskell by Mark Seemann
F# で書かれたコードベースを Haskell に移植したものです。
本記事は、関数型アーキテクチャを用いてやや複雑な問題にどのように取り組むかを探る 連載記事 の一部です。前回の記事では、C# によるベースラインのコードベースを提示しました。今後の記事ではこの C# のコードベースを出発点としてリファクタリングを進めていきますが、同時に、F# や Haskell など、他の言語ではどうなるのかも示していきたいと考えています。本記事では、そのベースラインを Haskell に移植する方法を紹介します。正直に言うと、最初にC# のコードを F# に移植してから、その F# のコードをガイドにして Haskell のコードを実装しました。
Git リポジトリを参照している場合、本記事のコードは .NET 用のリポジトリとは別のものであり、master ブランチからの抜粋です。
もし Haskell に興味がなければ、連載の基点となる記事に戻り、関心のある次のトピックに進んでいただいて構いません。
データ構造
Haskell のような静的型付けの関数型言語で開発する場合、まずデータ構造の定義から始めるのが自然です。
data User = User
{ userName :: String
, userScrobbleCount :: Int }
deriving (Show, Eq)
これは F# や C# のレコード定義とよく似ており、F# や C# における対応する型を反映したものです。最大の違いは、ユーザーの総スクロブル数（再生履歴のカウント）を表すフィールドが、TotalScrobbleCount ではなく userScrobbleCount と名付けられている点です。この変更の背景には、Haskell におけるデータの「ゲッター」がトップレベルの関数であるという事実があります。そのため、どのデータ構造に属するゲッターかを明示するため、通常はその構造体の名前を関数名のプレフィックスとして付けるのが良いとされています。今回の構造体の名前が User なので、ゲッター関数も user で始まるようにしています。
userTotalScrobbleCount では少し冗長に感じたため、Total を省略しましたが、それが適切かどうかはまだ分かりません。プログラミングにおける命名は常に難しく、最初に決めた名前が正しいとは限りません。ただし、再利用を前提としたライブラリを公開するわけでない限り、後で名前を変更する余地は十分あります。
残りの 2 つのデータ構造もほぼ同様です。
data Song = Song
{ songId :: Int
, songHasVerifiedArtist :: Bool
, songRating :: Word8 }
deriving (Show, Eq)
data Scrobble = Scrobble
{ scrobbledSong :: Song
, scrobbleCount :: Int }
deriving (Show, Eq)
scrobbleSong よりも scrobbledSong の方がより説明的でわかりやすいと感じたため、慣習から少し外れたこの名前を使っています。この選択によって特に問題は起きていませんが、良い判断だったかどうかは今も判断しかねています。
C# のインターフェイスを Haskell に移植するにはどうすればよいでしょうか。型クラスは C# や Java のインターフェイスと完全に同じではないものの、かなり近い機能であり、その役割を果たすことができます。Haskell においてこのような型クラスを使うのはあまり慣用的ではないと考えていますが、C# のインターフェイスに対応するものとしては十分機能します。
class SongService a where
getTopListeners :: a -> Int -> IO [User]
getTopScrobbles :: a -> String -> IO [Scrobble]
SongService クラスのインスタンスは、特定の曲に対するリスナーの一覧や、ユーザーごとのスクロブル数のランキングを取得するクエリに対応しています。
改めて述べておくと、この型クラスは可能であれば将来的に廃止するつもりですが、学習の目的上、一部のリファクタリング記事では引き続き登場します。そのことで、Haskell のコードと C# や F# のコードを比較しやすくなるはずです。
テストダブル
テストを行うためには、テストダブルが必要になります。そこで、フェイクオブジェクトとして以下のサービスを定義しました。これは単なる決定的なインメモリの実装です。型自体は、2 つのマップをラップしたものにすぎません。
data FakeSongService = FakeSongService
{ fakeSongs :: Map Int Song
, fakeUsers :: Map String (Map Int Int) }
deriving (Show, Eq)
C# の対応するクラスと同様に、fakeSongs は曲 ID から Song へのマップであり、fakeUsers はやや複雑です。これはユーザー名をキーとしたマップで、値はさらに別のマップになっています。その内側のマップでは、キーが曲 ID、値がそのユーザーによるスクロブル回数を表します。
この FakeSongService 構造体は、明示的に SongService のインスタンスとして実装されています。
instance SongService FakeSongService where
getTopListeners srvc sid = do
return $
uncurry User <$>
Map.toList (sum <$> Map.filter (Map.member sid) (fakeUsers srvc))
getTopScrobbles srvc userName = do
return $
fmap (\(sid, c) -> Scrobble (fakeSongs srvc ! sid) c) $
Map.toList $
Map.findWithDefault Map.empty userName (fakeUsers srvc)
特定の曲のトップリスナーを取得するには、fakeUsers の中から、その曲 ID (sid) を保持しているユーザーをすべて探し出し、それぞれのスクロブル数を合計し、それらのデータから User を生成します。
一方、あるユーザーのスクロブルランキングを取得するには、まず fakeUsers から該当するユーザーを探し出し、そのユーザーがスクロブルした曲をすべて fakeSongs の中から検索し、その情報から Scrobble を生成します。
そして、テストコードでは FakeSongService にデータを追加する手段も必要となるため、テスト専用のユーティリティ関数を定義しました。
scrobble userName s c (FakeSongService ss us) =
let sid = songId s
ss' = Map.insertWith (\_ _ -> s) sid s ss
us' = Map.insertWith (Map.unionWith (+)) userName (Map.singleton sid c) us
in FakeSongService ss' us'
ユーザー名、曲、スクロブル回数、FakeSongService を受け取り、新しいデータを追加した FakeSongService を返す関数です。
QuickCheck の Arbitrary インスタンス
F# のテストコードでは FsCheck を用いてコードの網羅性を高めていましたが、Haskell では QuickCheck を使います。
F# のテストのアイデアを移植する形で、まずユーザー名の QuickCheck ジェネレータを定義しました。
alphaNum :: Gen Char
alphaNum = elements (['a'..'z'] ++ ['A'..'Z'] ++ ['0'..'9'])
userName :: Gen String
userName = do
len <- choose (1, 19)
first <- elements $ ['a'..'z'] ++ ['A'..'Z']
rest <- vectorOf len alphaNum
return $ first : rest
アルゴリズムがアルファベットで始まる 20 文字以内の英数字のみを許容する必要があるわけではありません。ただし、テストが失敗したとき、改行や非表示文字を含んだ文字列を目にするよりは、"Yvj0D1I" や "tyD9P1eOqwMMa1Q6u" のような見やすい文字列のほうがありがたいという理由です。
QuickCheck を扱う上では、テスト対象システムの型をテスト専用の Arbitrary ラッパーで包むのが便利な場合があります。
newtype ValidUserName = ValidUserName { getUserName :: String } deriving (Show, Eq)
instance Arbitrary ValidUserName where
arbitrary = ValidUserName <$> userName
Song 型についても、簡単な Arbitrary インスタンスである AnySong を定義しました。
プロパティベーステストを少し
FakeSongService が用意できたので、F# のテストコードの先頭から順に、可能な限り忠実にテストコードを移植していきました。最初に実装したのは アイスブレイクテスト で、これはテスト対象のシステムが存在し、呼び出しに応じてクラッシュしないことを確認するだけのものです。
testProperty "No data" $ \ (ValidUserName un) -> ioProperty $ do
actual <- getRecommendations emptyService un
return $ null actual
2019 年以降ずっとそうしているように、テストケースを匿名関数としてインライン化しています。今回はそれを QuickCheck のプロパティとして表現しています。このテストでは、データを一切含まない FakeSongService を生成し、レコメンデーションを要求します。期待される結果は actual が空、つまり null であることです。なぜなら、レコメンドする対象が存在しないからです。
次のプロパティでは、サービスにいくつかデータを追加してからレコメンデーションを要求します。
testProperty "One user, some songs" $ \
(ValidUserName user)
(fmap getSong -> songs)
-> monadicIO $ do
scrobbleCounts <- pick $ vectorOf (length songs) $ choose (1, 100)
let scrobbles = zip songs scrobbleCounts
let srvc = foldr (uncurry (scrobble user)) emptyService scrobbles
actual <- run $ getRecommendations srvc user
assertWith (null actual) "Should be empty"
ここで注目すべき点が 2 つあります。まず、ビュー・パターンを使って Arbitrary のリストから曲のリストを射影している点です。getSong は AnySong newtype ラッパーに対応するゲッターです。
ビュー・パターンは、単一の Arbitrary インスタンスをリストに「昇格」させる宣言的な方法としてとても便利です。さらに 3 つ目のプロパティでは、それをさらに進めた例を示しています。
(fmap getUserName -> NonEmpty users)
この例では、ValidUserName ラッパーをリストに変換するだけでなく、それを NonEmpty に射影することで users が空でないリストであることを明示しています。QuickCheck はこの情報を基に、適切な値を生成します。
このより高度なビュー・パターンを使った実例に興味があれば、Git リポジトリを参照してください。
もう一点、“One user, some songs” テストは monadicIO の中で実行されています。これは今回のテストを書くまで存在を知らなかったもので、pick、run、assertWith とあわせて Test.QuickCheck.Monadic に定義されています。これにより、IO を伴うプロパティを記述することができます。今回のプロパティでは、getRecommendations が IO を返すため、この仕組みが必要となりました。
他にも QuickCheck のプロパティはありますが、ここで紹介した内容の繰り返しに過ぎません。詳細が必要な場合は、Git リポジトリを参照してください。
実例ベーステスト
プロパティベースのテストに加えて、F# で書かれていた通常のユニットテストも移植しました。以下はそのひとつです。
"One verified recommendation" ~: do
let srvc =
scrobble "ana" (Song 2 True 5) 9_9990 $
scrobble "ana" (Song 1 False 5) 10 $
scrobble "cat" (Song 1 False 6) 10 emptyService
actual <- getRecommendations srvc "cat"
[Song 2 True 5] @=? actual
このテストは単純なものですが、以前にオリジナルコードの仕様化を説明した記事でも述べたように、一部の実例ベーステストは実装上の癖や仕様の特徴をドキュメント化する意味合いを持っています。以下のテストは、そうした特徴を表すものを Haskell に移植した例です。
"Only top-rated songs" ~: do
-- Scale ratings to keep them less than or equal to 10.
let srvc =
foldr (\i -> scrobble "hyle" (Song i True (toEnum i `div` 2)) 500) emptyService [1..20]
actual <- getRecommendations srvc "hyle"
assertBool "Should not be empty" (not $ null actual)
-- ユーザーは1人だけだが、関連する曲が20曲あるため、実装上は同じ曲のリストに対して
-- 20回ループ処理を行うことになり、結果として（重複を含む）合計400曲となる。
-- これを評価で並べ替えると、上位200曲（つまり評価が5～10の曲）のみが残る。
-- なお、これは仕様化テストであり、実際の推薦システムのあるべき動作を
-- 必ずしも反映しているわけではない点に留意。
assertBool "Should have 5+ rating" (all ((>= 5) . songRating) actual)
このテストでは、ある 1 人のユーザーに対して合計 20 件のスクロブルを作成しています。具体的には、評価値が 0 の曲が 1 件、評価値 1 の曲が 2 件、評価値 2 の曲が 2 件……と続き、評価値 10 の曲が 1 件、という具合です。
GetRecommendationsAsync の実装では、これら 20 曲の「トップソング」をもとに、それらの曲をスクロブルした「他のユーザー」を探します。しかし今回は 1 人のユーザーしか存在しないため、それぞれの 20 曲に対して、毎回その 20 曲すべてが返され、結果として 400 曲分のレコメンデーションが得られる、という動作になります。
このように、より多くのユニットテストが存在します。すべての詳細を確認したい場合は、Git リポジトリをご覧ください。
実装
C# や F# の「リファレンス実装」に可能な限り忠実に対応する Haskell 実装を考えた結果、以下のようになりました。
getRecommendations srvc un = do
-- 1. 自ユーザーのトップスクロブルを取得
-- 2. 同じ曲を聴いた他ユーザーを取得
-- 3. そのユーザーのトップスクロブルを取得
-- 4. 曲を集約してレコメンドを生成
-- Impure
scrobbles <- getTopScrobbles srvc un
-- Pure
let scrobblesSnapshot = take 100 $ sortOn (Down . scrobbleCount) scrobbles
recommendationCandidates <- newIORef []
forM_ scrobblesSnapshot $ \scrobble -> do
-- Impure
otherListeners <- getTopListeners srvc $ songId $ scrobbledSong scrobble
-- Pure
let otherListenersSnapshot =
take 20 $
sortOn (Down . userScrobbleCount) $
filter ((10_000 <=) . userScrobbleCount) otherListeners
forM_ otherListenersSnapshot $ \otherListener -> do
-- Impure
otherScrobbles <- getTopScrobbles srvc $ userName otherListener
-- Pure
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
-- Pure
return $ take 200 $ sortOn (Down . songRating) recommendations
オリジナルの実装をできる限り忠実に再現するために、recommendationCandidates を IORef として定義し、ネストされたループの中で追加していけるようにしました。コードの末尾にある modifyIORef は、リストに曲を 1 曲追加する部分です。
ループがすべて終わった後、readIORef を使って recommendations を取り出します。
また、元の C# コードに書かれていたコメントも可能な限り移植しています。
このコードは Haskell の慣用的な書き方とは言えませんが、本記事の目的は C# のコードにできるだけ忠実に対応させることでした。リファクタリングを進める中で、より Haskell らしい実装をご紹介する予定です。
結論
これまでに紹介した前 2 回の記事と本記事により、今後リファクタリングを行うためのベースラインが整いました。C# の元コードはその言語においては慣用的であると考えられますが、今回の Haskell 版はそうではありません。しかし、C# や F# のコードと十分に似ているため、3 つの言語間で比較や対照を行いやすい構造になっています。
今回の Haskell 実装が「慣用的」と言えない要因は、特に 2 つあります。ひとつは IORef を使って曲のリストを更新している点、もうひとつは外部依存を型クラスで表現している点です。
今後の記事では、これら 2 点をどのように解消していけるか、さまざまなアーキテクチャの代替案を通してご紹介していきます。
次回： Impureim Sandwichにした曲レコメンデーション