标签云的累加器函数

Question

我正在尝试编写一个尾递归函数，它将查看不同单词的列表、所有单词的列表，以及 return 包含每个单词出现次数的列表。我实际上是在从目录中的文件中读取单词，但我似乎无法编译尾递归。这是我目前所拥有的：

let countOccurence (word:string) list = 
    List.filter (fun x -> x.Equals(word)) list

//(all words being a list of all words across several files)
let distinctWords = allWords |> Seq.distinct

let rec wordCloud distinct (all:string list) acc =
    match distinct with
    | head :: tail -> wordCloud distinct tail Array.append(acc, (countOccurence head all)) //<- What am I doing with my life?
    | [] -> 0

我意识到这可能是一个相当简单的问题，但我已经为这最后一块拼图苦苦思索了一个小时。有什么想法吗？

Answer 1

给定的声明存在几个问题：

使用 Array.append 来操作列表
错别字
不正确地使用空格将事物组合在一起

尝试将逻辑表达为一系列步骤，而不是将所有内容都放在一行不可读的代码中。这是我为理解上述表达式的问题所做的工作：

let rec wordCloud distinct (all:string list) acc =
    match distinct with
    | head :: tail ->
        let count = countOccurence head all
        let acc' = acc |> List.append count
        wordCloud distinct tail acc'
    | [] -> 0

这可以编译，但我不知道它是否按照您的要求执行...

请注意将 Array.append 替换为 List.append。

这仍然是尾递归，因为对 wordCloud 的调用位于尾部位置。

Answer 2

经过几个小时的工作，我想到了这个：

let countOccurance (word:string) list = 
    let count = List.filter (fun x -> word.Equals(x)) list
    (word, count.Length)

let distinctWords = allWords |> Seq.distinct |> Seq.toList

let print (tup:string*int) =
    match tup with
    | (a,b) -> printfn "%A: %A" a b

let rec wordCloud distinct (all:string list) (acc:(string*int) list) =
    match distinct with
    | [] -> acc
    | head :: tail -> 
        let accumSoFar = acc @ [(countOccurance head all)]
        wordCloud tail all accumSoFar

let acc = []
let cloud = (wordCloud distinctWords allWords acc)

let rec printTup (tupList:(string*int) list) =
    match tupList with
    | [] -> 0
    | head :: tail -> 
        printfn "%A" head
        printTup tail

printTup cloud

Answer 3

这个问题实际上有一个非常简单的解决方案，如果您退后一步，只需输入您想要执行的操作即可。

/// When you want to make a tag cloud...
let makeTagCloud (words: string list) =
    // ...take a list of all words...
    words 
    // ...then walk along the list...
    |> List.fold (fun cloud word ->
        // ...and check if you've seen that word...
        match cloud |> Map.tryFind word with
        // ...if you have, bump the count...
        | Some count -> cloud |> Map.add word (count+1)
        // ...if not, add it to the map...
        | None       -> cloud |> Map.add word 1) Map.empty
    // ...and change the map back into a list when you are done.
    |> Map.toList

读起来像诗 ;)

标签云的累加器函数

Accumulator function for tag cloud

f#

tail-recursion