F# 무료 모나드를 사용한 노래 추천 | Mark Seemann

프로그래밍 F#
1

F# Free Monad를 활용한 노래 추천 시스템

개요

함수형 프로그래밍의 대안적 설계 방식을 탐구하는 시리즈의 일부로, 대규모 스크로블 데이터셋에서 노래 추천을 계산하는 동일한 예제 문제를 다룬다. 이전 Haskell 구현에 이어 F#으로 free monad를 구현한다.

Git 저장소에서 fsharp-free 브랜치의 코드를 참조할 수 있으며, 시작점은 fsharp-port이다.

Functor

Free monad는 어떤 functor로부터도 monad를 정의할 수 있게 한다. 도메인 특화 언어(DSL)의 명령어 셋을 모델링하는 functor로 시작한다.

기존 인터페이스

type SongService =
    abstract GetTopListenersAsync : songId : int -> Task<IReadOnlyCollection<User>>
    abstract GetTopScrobblesAsync : userName : string -> Task<IReadOnlyCollection<Scrobble>>

Sum Type 정의

type SongInstruction<'a> =
    | GetTopListeners of songId : int * (IReadOnlyCollection<User> -> 'a)
    | GetTopScrobbles of userName : string * (IReadOnlyCollection<Scrobble> -> 'a)

인터페이스 메서드와 discriminated union 케이스 간의 유사성을 확인할 수 있다.

Map 함수 구현

module SongInstruction =
    let map f = function
        | GetTopListeners (  songId, next) -> GetTopListeners (  songId, next >> f)
        | GetTopScrobbles (userName, next) -> GetTopScrobbles (userName, next >> f)

F#에서는 Haskell과 달리 Functor를 직접 구현해야 한다.

Monad

데이터 구조

type SongProgram<'a> =
    | Free of SongInstruction<SongProgram<'a>>
    | Pure of 'a

functor를 래핑하여 명령어들을 시퀀싱할 수 있게 한다.

Bind 함수

module SongProgram =
    let rec bind f = function
        | Free inst -> inst |> SongInstruction.map (bind f) |> Free
        | Pure inst -> f inst

F# free monad 레시피를 충실히 따른 구현이다.

Computation Expression

Builder 클래스

type SongProgramBuilder () =
    member _.Bind (x, f) = SongProgram.bind f x
    member _.Return x = Pure x
    member _.ReturnFrom x = x
    member _.Zero () = Pure ()
    member _.Delay f = f
    member _.Run f = f ()
    member this.While (guard, body) =
        if not (guard ())
        then this.Zero ()
        else this.Bind (body (), fun () -> this.While (guard, body))
    member this.TryWith (body, handler) =
        try this.ReturnFrom (body ())
        with e -> handler e
    member this.TryFinally (body, compensation) =
        try this.ReturnFrom (body ())
        finally compensation ()
    member this.Using (disposable : #System.IDisposable, body) =
        let body' = fun () -> body disposable
        this.TryFinally (body', fun () ->
            match disposable with
            | null -> ()
            | disp -> disp.Dispose ())
    member this.For (sequence : seq<_>, body) =
        this.Using (sequence.GetEnumerator (), fun enum ->
            this.While (enum.MoveNext, this.Delay (fun () -> body enum.Current)))
    member _.Combine (x, y) = x |> SongProgram.bind (fun () -> y ())

명령형 언어 구조를 지원하기 위해 일반적인 요구사항보다 더 복잡하게 구현되었다.

Builder 인스턴스

let songProgram = SongProgramBuilder ()

Helper 함수

let getTopListeners songId = Free (GetTopListeners (songId, Pure))
 
let getTopScrobbles userName = Free (GetTopScrobbles (userName, Pure))

사용자 코드를 더 깔끔하게 만들어준다.

명령형 스타일 프로그램

초기 구현

let getRecommendations userName = songProgram {
    // 1. Get user's own top scrobbles
    // 2. Get other users who listened to the same songs
    // 3. Get top scrobbles of those users
    // 4. Aggregate the songs into recommendations
 
    let! scrobbles = getTopScrobbles 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 = getTopListeners 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
            // Impure
            let! otherScrobbles = getTopScrobbles otherListener.UserName
 
            // Pure
            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<_>
 
    return recommendations }

원래 GetRecommendationsAsync 메서드와 매우 유사하다. songService.GetTopScrobblesAsync 대신 getTopScrobbles를 사용한다.

참조 투명성

지역 상태 변이(recommendationCandidates)가 있지만 여전히 참조 투명하다. 참조 투명성은 특정 함수 호출을 반환값으로 대체할 수 있음을 의미한다. 함수가 반환값에 도달하기 위해 지역 변이를 사용했다는 것은 호출자에게 중요하지 않다.

Interpreter

구현

let rec interpret = function
    | Pure x -> x
    | Free (GetTopListeners (songId, next)) ->
        users
        |> Seq.filter (fun kvp -> kvp.Value.ContainsKey songId)
        |> Seq.map (fun kvp -> user kvp.Key (Seq.sum kvp.Value.Values))
        |> Seq.toList
        |> next
        |> interpret
    | Free (GetTopScrobbles (userName, next)) ->
        users.GetOrAdd(userName, ConcurrentDictionary<_, _> ())
        |> Seq.map (fun kvp -> scrobble songs[kvp.Key] kvp.Value)
        |> Seq.toList
        |> next
        |> interpret

FakeSongService 클래스에 추가된 메서드로, 원래 Fake 인터페이스 구현을 밀접하게 반영한다.

공개 메서드

member _.Interpret program = interpret program

테스트 리팩토링

FsCheck 프로퍼티 테스트

[<Property>]
let ``One user, some songs`` () =
    gen {
        let! user = Gen.userName
        let! songs = Gen.arrayOf Gen.song
        let! scrobbleCounts =
            Gen.choose (1, 100) |> Gen.arrayOfLength songs.Length
        return (user, Array.zip songs scrobbleCounts) }
    |> Arb.fromGen |> Prop.forAll <| fun (user, scrobbles) ->
        let srvc = FakeSongService ()
        scrobbles |> Array.iter (fun (s, c) -> srvc.Scrobble (user, s, c))
 
        let actual = getRecommendations user |> srvc.Interpret
 
        Assert.Empty actual

원래 task 기반이었던 테스트가 이제 순수 함수로 변경되었다.

예제 기반 테스트

[<Fact>]
let ``One verified recommendation`` () =
    let srvc = FakeSongService ()
    srvc.Scrobble ("cat", song 1 false 6uy,     10)
    srvc.Scrobble ("ana", song 1 false 5uy,     10)
    srvc.Scrobble ("ana", song 2  true 5uy, 9_9990)
 
    let actual = getRecommendations "cat" |> srvc.Interpret
 
    Assert.Equal<Song> ([ song 2 true 5uy ], actual)

모든 테스트 마이그레이션 후 RecommendationsProvider 클래스와 SongService 인터페이스는 더 이상 필요 없어 삭제되었다. Strangler 패턴을 사용하여 점진적으로 이동했다.

Traverse

Map 함수

let map f = bind (f >> Pure)

Traverse 함수

let traverse f xs =
    let concat xs ys = xs |> bind (fun x -> ys |> map (Seq.append x))
    Seq.fold
        (fun acc x -> concat acc (f x |> map Seq.singleton))
        (Pure (Seq.empty))
        xs

이중 중첩 루프를 리팩토링하기 위해 traversal이 필요하다.

리팩토링된 프로그램

최종 버전

let getRecommendations userName = songProgram {
    // 1. Get user's own top scrobbles
    // 2. Get other users who listened to the same songs
    // 3. Get top scrobbles of those users
    // 4. Aggregate the songs into recommendations
 
    let! scrobbles = getTopScrobbles userName
 
    let! otherlListeners =
        getUsersOwnTopScrobbles scrobbles
        |> SongProgram.traverse (fun s -> getTopListeners s.Song.Id)
 
    let! otherScrobbles =
        otherlListeners
        |> Seq.collect getOtherUsersWhoListenedToTheSameSongs
        |> SongProgram.traverse (fun u -> getTopScrobbles u.UserName)
 
    return
        otherScrobbles
        |> Seq.collect getTopScrobblesOfUsers
        |> aggregateTheSongsIntoRecommendations }

두 번의 traverse 적용이 이중 중첩 루프를 대체한다. getRecommendations의 타입은 변경되지 않았고 모든 테스트가 여전히 통과한다.

결론

Haskell과의 비교

예상대로 Haskell보다 더 많은 보일러플레이트 코드가 필요했다. 그럼에도 F# free monad 레시피를 따라 순조롭게 진행되었다. for 루프 지원을 위한 computation expression builder 구현 시 문제가 있었지만 free monad와는 무관한 문제였다.

실용적 고려사항

F# free monad 레시피의 결정 플로우차트를 참조하라. 이 글들은 규범적이기보다는 설명적이다. 가능한 것을 제시할 뿐, 선택은 독자의 몫이다.

타입 시스템의 이점

SongProgram<'a>는 인터페이스와 유사해 보이지만 훨씬 더 제한적이다. 의존성 주입을 사용하는 메서드는 본질적으로 불순하며 모든 종류의 버그를 포함할 수 있다. F# 타입 시스템은 제약되지 않은 부작용이나 비결정성을 체크하지 않지만, SongProgram<'a> 같은 타입은 SongProgram 관련 액션만 발생함을 강하게 시사한다.

언어별 적용 가능성

  • F#: 주로 니치 유스케이스로 여전히 유용
  • C#: 이런 종류의 프로그래밍을 가능하게 하는 언어 기능이 부족해 유용하지 않음
  • 시연 목적으로는 C#에서도 가능

다음 글

Song recommendations with C# free monads

1개의 좋아요