haskell - 在列表中找到對

我試圖尋找列表中的元素對，假設它們是列表中唯一的對，並且不超過3個相同的連續元素。haskell - 在列表中找到對

我有一個函數，它接受一個列表，並返回該對中第一個元素的索引（如果有的話）。如果沒有，則返回-1

searchForPairs xs = searchHelp xs ((genericLength xs) - 1) 
    where searchHelp xs n 
     | searchHelp xs 0 = -1    -- no pairs found 
     | (xs !! n) == (xs !! (n - 1)) = n 
     | otherwise = searchHelp xs n-1

出於某種原因，它返回的錯誤：

Couldn't match expected type `Bool' with actual type `Int' 
In the expression: n 
In an equation for `searchHelp': 
    searchHelp xs n 
     | searchHelp xs 0 = - 1 
     | (xs !! n) == (xs !! (n - 1)) = n 
     | otherwise = searchHelp xs n - 1 
In an equation for `searchForPairs': 
    searchForPairs xs 
     = searchHelp xs ((genericLength xs) - 1) 
     where 
      searchHelp xs n 
      | searchHelp xs 0 = - 1 
      | (xs !! n) == (xs !! (n - 1)) = n 
      | otherwise = searchHelp xs n - 1

好像它應該工作。任何想法，爲什麼不是？謝謝

來源

2012-10-07 user1670032

什麼是根本問題？你想達到什麼目的？ – AndrewC

避免返回像'-1'這樣的標記值來指示失敗。用'Maybe'代替。 – hammar

@AndrewC不是'只是5'而不是'Maybe 5'？ – epsilonhalbe

你有兩個問題。首先是在這一行：

 | otherwise = searchHelp xs n-1

編譯器interperets以此爲(searchHelp xs n) - 1，不searchHelp xs (n-1)，如你意。第二個問題是在你使用後衛：

 | searchHelp xs 0 = -1    -- no pairs found

由於searchHelp xs 0不是一個布爾表達式（你想使用它作爲一個模式），編譯器拒絕了。我可以看到兩個簡單的解決方案：

searchForPairs xs = searchHelp xs ((genericLength xs) - 1) 
    where searchHelp xs n 
     | n == 0 = -1    -- no pairs found 
     | (xs !! n) == (xs !! (n - 1)) = n 
     | otherwise = searchHelp xs (n-1)

和

searchForPairs xs = searchHelp xs ((genericLength xs) - 1) 
    where 
     searchHelp xs 0 = -1   -- no pairs found 
     searchHelp xs n 
     | (xs !! n) == (xs !! (n - 1)) = n 
     | otherwise = searchHelp xs (n-1)

現在，不幸的是，雖然這個工作，它是非常低效的。這是因爲你使用了!!。在Haskell中，列表是鏈接列表，因此xs !! n將採用n個步驟，而不是1.這意味着您的函數在列表的長度上所花費的時間是二次的。爲了改善這種情況，要沿列表向前循環，使用模式匹配：

searchForPairs xs = searchHelp xs 0 where 
    searchHelp (x1 : x2 : xs) pos 
     | x1 == x2 = pos 
     | otherwise = searchHelp (x2 : xs) (pos + 1) 
    searchHelp _ _ = -1

來源

2012-10-07 23:34:06 gereeter

@gereeter已經說明你的錯誤，我只是想指出的是，你應該的情況下，答案不返回-1未找到。相反，如果沒有答案，則應返回Nothing，如果答案爲pos，則返回Just pos。這可以保護您避免多種錯誤。

來源

2012-10-08 03:51:49

我無法完全理解你想要做什麼，但是從代碼看來，你似乎試圖在列表中找到兩個相同的連續元素。您可以使用模式匹配來提取列表的前兩個元素，而不是使用!!爲列表建立索引，您可以使用模式匹配來提取列表的前兩個元素，檢查它們是否相等，如果不是，則繼續搜索餘數（包括第二個元素）。如果列表中沒有至少有兩個元素，將返回Nothing

searchForPairs xs = go 0 xs where 
    go i (x1:[email protected](x2:_)) | x1 == x2 = Just i 
         | otherwise = go (i+1) xs 
    go _ _ = Nothing

來源

2012-10-08 04:49:22 pat

對於它的價值，這裏是一個略微地道（和自由點）實現的你正在嘗試做的事：

searchPairs :: Eq a => [a] -> Maybe Int 
searchPairs = interpret . span (uncurry (/=)) . (zip <*> tail) 
    where 
    interpret (flag, res) = if null flag then Nothing else Just $ length res

說明：zip <*> tail創建連續元素對的列表（使用讀者應用程序類型類）。 uncurry (/=)測試這樣的一對是否由相同的元素組成。最後，interpret將結果轉換爲值爲Maybe Int類型。

來源

2014-07-22 10:13:59

haskell - 在列表中找到對

回答

相關問題