Haskell中最長的公共前綴

Question

我試圖根據最長的公共前綴cpfx匹配文件，並且對haskell有點新。我正在嘗試列出清單並簡單地返回它們共享的前綴。例如：

cpfx ["obscure","obscures","obscured","obscuring"] --> "obscur" 

cpfx ["abc", "ab", "abcd"] --> "ab" 

我想這與一對夫婦的輔助方法，像這樣：

cpfx :: [[Char]] -> [Char] 
cpfx [] = [] -- nothing, duh 
cpfx (x:[]) = x -- only one thing to test, return it 
cpfx (x:t) = cpfx' (x:t) 0 -- otherwise, need to test 

cpfx' (x:[]) _ = [] 
cpfx' (x:t) n 
-- call ifMatch to see if every list matches at that location, then check the next one 
     | ifMatch (x:t) n = x!!n + cpfx' x (n+1) 
     | otherwise = [] 

-- ifMatch means if all words match at that location in the list 
ifMatch (x:[]) _ = True 
ifMatch (x:xs:[]) n = x!!n == xs!!n 
ifMatch (x:xs:t) n 
     | x!!n == x!!n = ifMatch xs n 
     | otherwise = False 

但我得到的錯誤： Occurs check: cannot construct the infinite type: a0 = [a0]

，我猜是屬於ifMatch (x:t) n = x!!n + cpfx' x (n+1)行。

我能做些什麼來糾正這種情況？

Answer 1

您提到的這一行確實是一個問題。

注意，參數cpfx'爲(x:[])，即一個東西所有的列表具有相同的類型x，但你的遞歸調用只使用x。因此，您將得到無限類型的錯誤：您正試圖識別類型爲[x]的x的類型。 （爲了具體，假設x是String然後你提示x具有類型String（由於參數的圖案匹配）和[String]（由x是如何在遞歸調用中使用）。

I」不十分清楚你想要做什麼，但你也有因爲x!!n + ...同一線路有問題。在這裏，x!!n是（可能）一Char，但您使用的是+運營商，這不是爲Char定義你可能意味着++的名單追加，除了x!!n是不列表，它是一個單一的元素。因此，你可能意味着

[x!!n] ++ cpfx' ... 

或

(x!!n) : cpfx' ... 

Answer 2

這裏是另一種方式來思考問題：

假設你有一個最長公共前綴的功能：

lcp :: String -> String -> String 

您可以擴展此列表如下：

cpfx [a]  = a 
cpfx [a,b]  = lcp a b 
cpfx [a,b,c] = lcp (lcp a b) c 
cpfx [a,b,c,d] = lcp (lcp (lcp a b) c) d 
... 

這一般遞歸模式被稱爲摺疊。

Answer 3

可避免使用顯式的遞歸很容易：

import Data.Maybe (isJust, fromJust) 
commonPrefix = map fromJust . takeWhile isJust . map the . transpose' 

the接受一個列表，並返回Nothing如果列表中的元素不同，否則返回獨特的元素：

the :: Eq a => [a] -> Maybe a 
the [] = Nothing 
the (x:xs) 
    | and $ map (==x) xs = Just x 
    | otherwise   = Nothing 

transpose'與Data.List.transpose類似，但它將結果截斷爲最短列表的長度：

transpose' xs = maybe [] id $ do 
    ys <- mapM ht xs 
    return $ (map fst ys) : (transpose' (map snd ys)) 
    where 
     ht [] = Nothing 
     ht (x:xs) = Just (x,xs) 

transpose ["abc", "ab", "abcd"] == ["aaa","bbb","cc","d"]但transpose' ["abc", "ab", "abcd"] == ["aaa","bbb"]

Answer 4

如何解決這些錯誤

注：雖然我會告訴你如何認識和解決這些錯誤，我也呈現出更優雅版（至少從我的角度來看）以下。

當你結束了一個無限的類型，這是一個好主意太添加類型簽名：

cpfx' :: [[Char]] -> Int -> [Char] 
ifMatch :: [[Char]] -> Int -> Bool 

突然，我們獲得了更多的錯誤，兩人在

| ifMatch (x:t) n = x!!n + cpfx' x (n+1) 

 
Couldn't match expected type `[Char]' with actual type `Char' 
    Expected type: [[Char]] 
     Actual type: [Char] 
    In the first argument of `(!!)', namely `x' 
    In the first argument of `(+)', namely `x !! n' 

 No instance for (Num [Char]) 
     arising from a use of `+' 

and in ifMatch：

| x!!n == x!!n = ifMatch xs n 

 Couldn't match expected type `[Char]' with actual type `Char' 
    Expected type: [[Char]] 
     Actual type: [Char] 
    In the first argument of `ifMatch', namely `xs' 
    In the expression: ifMatch xs n 

現在，cpfx'錯誤很簡單：x是[Char]，x !! n是Char，並希望利弊它放到一個列表，所以使用:代替+。此外，您要申請cpfx'至t，而不是x。這也解決了你的第二個錯誤。在ifMatch,x!!n == x!!n是多餘的，並且xs具有類型[Char]，因此對於ifMatch沒有正確的類型。這也是一個錯字：

| x!!n == xs!!n = ifMatch t n 

但是，現在我們修復了這些編譯錯誤，您的程序是否真的有意義？尤其是，你能指望什麼這行做的事：

ifMatch (x:xs) n = x!!n : cpfx' xs (n+1) 

(x:xs)是你的話清單。但是，您在每次迭代中都會刪除一個詞，這顯然不是您的意思。你想

ifMatch (x:xs) n = x!!n : cpfx' (x:xs) (n+1) 

整體而言，我們得到如下代碼：

cpfx :: [[Char]] -> [Char] 
cpfx []  = [] 
cpfx [x] = x 
cpfx (x:xs) = cpfx' (x:xs) 0 

cpfx' :: [[Char]] -> Int -> [Char] 
cpfx' [x] _ = [] 
cpfx' (x:xs) n 
    | ifMatch (x:xs) n = x!!n : cpfx' (x:xs) (n+1) 
    | otherwise = [] 

ifMatch :: [[Char]] -> Int -> Bool 
ifMatch [x]  _ = True 
ifMatch [x,y] n = x!!n == y!!n 
ifMatch (x:y:xs) n 
     | x!!n == y!!n = ifMatch xs n 
     | otherwise = False 

使用更簡單的方法摺疊

讓我們讓我們的功能有點簡單，但也比較一般寫爲commonPrefix實現的任何類型==：

commonPrefix :: (Eq e) => [e] -> [e] -> [e] 
commonPrefix _ [] = [] 
commonPrefix [] _ = [] 
commonPrefix (x:xs) (y:ys) 
    | x == y = x : commonPrefix xs ys 
    | otherwise = [] 

如果y你不習慣那種符號，想象一下e是Char。現在，一些詞的共同的前綴可以寫成：

"hello" `commonPrefix` "hell" `commonPrefix` "hero" 

現在的問題是，如果你想爲一系列的事情做的事情，你平時用fold：

foldl :: (a -> b -> a) -> a -> [b] -> a 

foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn 

最後一個例子看起來和我們的\ commonPrefix` line before! However, we do not have a starting value, so we would use the first element of our list instead. Luckily, there's already [ foldl1`] 2完全一樣。因此，我們以前複雜的功能可以歸結爲：

commonPrefixAll :: (Eq a) => [[a]] -> [a] 
commonPrefixAll = foldl1 commonPrefix 

你應該從這個記住的是：每當你想要走過去列表中的多個元素，以提供一個值，想一想它是否是真的在每次迭代中都必須查看所有元素。通常，一次只關注兩個元素就足夠了，然後使用正確的摺疊。有關更多示例和信息，請參閱部分Computing one answer over a collection in Real World Haskell。

Answer 5

什麼像一個簡單的功能：

import Data.List 

cpfx xs = comp (reverse $ minimum xs) (map reverse xs) 
where comp ys xs 
    | True == (all (==True) $ map (\x->isSuffixOf ys x) xs) 
        = reverse ys 
    | ys == [] = [] 
    | otherwise = comp (tail ys) xs 

...它正常工作：codepad.org