學習haskell：創建skip-bigrams的遞歸函數

Question

我正在通過NLPWP Book的方式工作，我在處理遞歸函數的章節中。用於計算的雙字母組遞歸函數如下：

bigram :: [a] -> [[a]] 
bigram [] = [] 
bigram [_] = [] 
bigram xs = take 2 xs : bigram (tail xs) 

如果我在wordlist = ["colorless", "green", "ideas", "sleep", "furiously"]運行它，我得到這個：

bigram chomsky 

[("colorless","green"),("green","ideas"),("ideas","sleep"),("sleep","furiously")] 

演習說：

A skip-bigram is any pair of words in sentence order. Write a function skipBigrams that extracts skip-bigrams from a sentence as a list of binary tuples, using explicit recursion. Running your function on ["Colorless", "green", "ideas", "sleep", "furiously"] should give the following output:

Prelude> skipBigrams ["Colorless", "green", "ideas", "sleep", "furiously"] [("Colorless","green"),("Colorless","ideas"),("Colorless","sleep"),("Colorless","furiously"),("green","ideas"),("green","sleep"),("green","furiously"),("ideas","sleep"),("ideas","furiously"),("sleep","furiously")]

這裏是定義我試過了：

skipBigram [] = [] 
skipBigram [_] = [] 
skipBigram (x:xs) = [(x, (head xs)), (x, skipBigram xs)] 

但我發現了以下錯誤：

Occurs check: cannot construct the infinite type: t ~ [(t, t)] 
Relevant bindings include 
    xs :: [t] (bound at :3:15) 
    x :: t (bound at :3:13) 
    skipBigram :: [t] -> [(t, t)] (bound at :1:1) 
In the expression: interactive:IHaskell384.skipBigram xs 
In the expression: (x, interactive:IHaskell384.skipBigram xs) 

其中，新哈斯克爾，因爲我，我沒有絲毫瞭解。什麼是無限類型？相關的綁定？

我應該如何界定skipBigram解決這個編譯時錯誤？

Answer 1

Try this definition:

skipBigram :: [a] -> [(a,a)] 
skipBigram  [] = [] -- nothing to do with an empty list 
skipBigram (x:xs) = [(x,y) | y <- xs] ++ skipBigram xs 

你skipBigram功能生成所有的「2元組左到右的組合」列表中的單詞。我們可以用遞歸定義中的simple list comprehension來捕獲這個概念。通過遞歸地連接簡單的列表解析，我們獲得了期望的結果列表。

Answer 2

你得到這個是因爲你的結果是一個成對的列表，其中第一個項目的第二部分是某個元素，而第二個項目的結果列表的第二部分是，無論你正在努力回饋（你使用遞歸這裏，所以它必須是同一類型） - 所以你說：

my result is a list-of-tuples, but part of those tuples is the result-type itself

那是什麼錯誤告訴你

---

這裏還有一些細節：

看看你的最後一行

skipBigram (x:xs) = [(x, (head xs)), (x, skipBigram xs)] 

你的元組在右側的列表，以便它的類型就會像（基於結果列表中的第一個元素）：

skipBigram :: [a] -> [(a,a)] 

但在你有第二個項目(x, skipBigram xs)這意味着它將有(a, [(a,a)])的類型（記住skipBigram xs的類型就是上面的部分）。

等 - 比較元組的第二部分 - 你有a ~ [(a,a)]產生的錯誤，因爲不知何故類型a應該是一樣的[(a,a)]，你可以在所有的永恆擴大;）

---

現在算法本身：

它不會這樣工作 - 你不知何故必須得到所有的組合，要做到這一點，你必須使用列表中的項目。

通常，您可以使用list-comprehensions或list-monad的do-notation來做到這一點。

得到持續想一想：

f [] = [[]] 
f (x:xs) = 
    let xss = f xs 
    in [ x:xs | xs <- xss ] ++ xss 

測試，並在ghci中發揮它 - 你將不得不使用這個你得到了什麼莫名其妙

（OK recursion.ninja結合^^寵壞你的樂趣 - 無論如何，如果你不介意，我會放過這裏）

Answer 3

無限類型錯誤是抱怨你使用了列表。你的函數的類型應該是[a] -> [a] -> [(a, a)]，但是當GHC試圖推斷你的函數的類型時，它會得到那個無限類型的a = [a]。相關的綁定只是可能導致錯誤的其他變量的類型。

但是，即使忽略類型錯誤，你的函數也不會做你想要的。首先，你的函數總是返回一個長度爲2的列表，因爲你已經明確地構造了列表。此外，結果將包括("Colorless", "Colorless")，因爲(x, head xs)在這裏與(x, x)相同。

相反，嘗試這種解決方案

skipBigram :: [a] -> [(a, a)] 
skipBigram [] = [] 
skipBigram (x:xs) = map (x,) xs ++ skipBigram xs 

對於此功能工作，你需要放線

{-# LANGUAGE TupleSections #-} 

在你的文件的開頭。