特定型別結構的合并演算法-有解無憂

我正在嘗試為特定格式的結構撰寫合并演算法：

data ExcerptNode = ExcerptNode (Maybe Int) (Either Excerpt [Int]) deriving (Show, Eq)
data Excerpt = Excerpt [ExcerptNode] deriving (Show, Eq)

這個想法是能夠將串列Maybe Int轉換為Excerpt并能夠合并摘錄及其串列：

maybeIntListToExcerptNode :: [Maybe Int] -> ExcerptNode
maybeIntListToExcerptNode [] = ExcerptNode Nothing (Right [])
maybeIntListToExcerptNode (x:xs) = if all (==Nothing) xs 
  then ExcerptNode x (Right [])
  else ExcerptNode x (Left $ Excerpt [ maybeIntListToExcerptNode xs ])

mergeExcerptNodes :: ExcerptNode -> ExcerptNode -> [ExcerptNode]
mergeExcerptNodes a@(ExcerptNode x (Right xls)) b@(ExcerptNode y (Right yls)) = if x == y 
  then [ExcerptNode x (Right (nub $ sort (xls    yls)))]
  else [a, b]
mergeExcerptNodes a@(ExcerptNode x (Left xls)) b@(ExcerptNode y (Right yls)) = if x == y 
  then [ExcerptNode x (Left xls)]
  else [a, b]
mergeExcerptNodes a@(ExcerptNode x (Right xls)) b@(ExcerptNode y (Left yls)) = if x == y 
  then [ExcerptNode y (Left yls)]
  else [a, b]
mergeExcerptNodes a@(ExcerptNode x (Left xls)) b@(ExcerptNode y (Left yls)) = if x == y 
  then [ExcerptNode x (Left (mergeExcerpts xls yls))]
  else [a, b]

mergeExcerpts :: Excerpt -> Excerpt -> Excerpt 
mergeExcerpts (Excerpt []) (Excerpt y) = Excerpt y
mergeExcerpts (Excerpt x) (Excerpt []) = Excerpt x
mergeExcerpts (Excerpt a) (Excerpt b) = Excerpt $ mergeExcerptNodesLists a b

mergeExcerptNodesLists :: [ExcerptNode] -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodesLists [] [] = []
mergeExcerptNodesLists x [] = x
mergeExcerptNodesLists [] y = y
mergeExcerptNodesLists (x:xs) b@(y:ys) = mergeExcerptNodesLists (mergeExcerptNodeIntoList x b) (mergeExcerptNodesLists xs b)

mergeExcerptNodeIntoList :: ExcerptNode -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodeIntoList x [] = [x]
mergeExcerptNodeIntoList a@(ExcerptNode x (Right xls)) (b@(ExcerptNode y (Right yls)):ys) = if x == y 
  then [ExcerptNode x (Right (nub $ sort (xls    yls)))]    ys
  else mergeExcerptNodeIntoList a ys 
mergeExcerptNodeIntoList a@(ExcerptNode x (Left xls)) (b@(ExcerptNode y (Right yls)):ys) = if x == y 
  then [ExcerptNode x (Left xls)]    ys
  else mergeExcerptNodeIntoList a ys 
mergeExcerptNodeIntoList a@(ExcerptNode x (Right xls)) (b@(ExcerptNode y (Left yls)):ys) = if x == y 
  then [ExcerptNode y (Left yls)]    ys
  else mergeExcerptNodeIntoList a ys 
mergeExcerptNodeIntoList a@(ExcerptNode x (Left xls)) (b@(ExcerptNode y (Left yls)):ys) = if x == y 
  then [ExcerptNode x (Left (mergeExcerpts xls yls))]    ys
  else mergeExcerptNodeIntoList a ys

該演算法的問題在于以下行：

mergeExcerptNodesLists (x:xs) b@(y:ys) = mergeExcerptNodesLists (mergeExcerptNodeIntoList x b) (mergeExcerptNodesLists xs b)

由于這條線演算法掛起，我不太清楚如何修復它才能成功合并。例如，它掛在以下輸入上：

a = maybeIntListToExcerptNode [Nothing, Nothing, Just 0]; b = maybeIntListToExcerptNode [Nothing, Nothing, Just 1];
mergeExcerptNodes a b

我期待的結果是：

[ExcerptNode Nothing (Left (Excerpt [ExcerptNode Nothing (Left (Excerpt [ExcerptNode (Just 1) (Right []),ExcerptNode (Just 0) (Right [])]))]))]

我試圖將其更改為mergeExcerptNodesLists (x:xs) b@(y:ys) = (mergeExcerptNodeIntoList x b) (mergeExcerptNodesLists xs b)，但在這種情況下，它不會合并而是追加。如果我將其更改為mergeExcerptNodesLists (x:xs) b@(y:ys) = mergeExcerptNodesLists (mergeExcerptNodeIntoList x b) (mergeExcerptNodesLists xs ys)，它會省略元素。

任何想法如何改進演算法以能夠Excerpts成功合并？

uj5u.com熱心網友回復：

我認為您需要進行修改mergeExcerptNodeIntoList，以便它根據x==y測驗決定是否將節點合并到串列中，并將其合并或附加到串列中。新版本可能如下所示：

mergeExcerptNodeIntoList :: ExcerptNode -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodeIntoList a [] = [a]
mergeExcerptNodeIntoList (ExcerptNode x u) (ExcerptNode y v : bs)
  | x == y = [ExcerptNode x (mergeBranches u v)]    bs
  where mergeBranches :: Either Excerpt [Int] -> Either Excerpt [Int] -> Either Excerpt [Int]
        mergeBranches (Right xls) (Right yls) = Right . nub . sort $ xls    yls
        mergeBranches (Left xls)  (Right _)   = Left xls
        mergeBranches (Right _)   (Left yls)  = Left yls
        mergeBranches (Left xls)  (Left yls)  = Left $ mergeExcerpts xls yls
mergeExcerptNodeIntoList a (b:bs) = b : mergeExcerptNodeIntoList a bs

現在，由于該節點a已被此函式“處理”，因此您無需在中一遍又一遍地重新合并它mergeExcerptNodesList，您可以將其重寫為：

mergeExcerptNodesLists :: [ExcerptNode] -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodesLists [] [] = []
mergeExcerptNodesLists x [] = x
mergeExcerptNodesLists [] y = y
mergeExcerptNodesLists (x:xs) b = mergeExcerptNodesLists xs (mergeExcerptNodeIntoList x b)

在這些修改之后，您的測驗用例可以正常作業，但可以進行許多額外的重構。例如，現在很容易重新mergeExcerptNodes定義mergeExcerptNodeIntoList：

mergeExcerptNodes :: ExcerptNode -> ExcerptNode -> [ExcerptNode]
mergeExcerptNodes a b = mergeExcerptNodeIntoList a [b]

（與以前的版本相比，這翻轉了它們無法合并的順序a和時間。如果這很重要，請使用。）bmergeExcerptNodeIntoList b [a]

另外，mergeExcerpts處理了很多不需要作為特例處理的特例，所以可以更簡單地改寫為：

mergeExcerpts :: Excerpt -> Excerpt -> Excerpt
mergeExcerpts (Excerpt a) (Excerpt b) = Excerpt $ mergeExcerptNodesLists a b

實際上，mergeExcerptNodesList 也處理了一堆不需要特殊處理的特殊情況，而且真的只是一個 fold over mergeExcerptNodeIntoList：

mergeExcerptNodesLists :: [ExcerptNode] -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodesLists as bs = foldr mergeExcerptNodeIntoList as bs

同樣，這個重構在技術上顛倒了順序，所以寫：

mergeExcerptNodesLists :: [ExcerptNode] -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodesLists as bs = foldr mergeExcerptNodeIntoList bs as

如果這很重要。這可以減少 eta，但現在很容易組合mergeExcerpts成mergeExcerptNodesLists一個函式：

mergeExcerpts :: Excerpt -> Excerpt -> Excerpt
mergeExcerpts (Excerpt as) (Excerpt bs) = Excerpt $ foldr mergeExcerptNodeIntoList as bs

我的重構代碼的最終副本如下所示：

{-# OPTIONS_GHC -Wall #-}

import Data.List

newtype Excerpt = Excerpt [ExcerptNode] deriving (Show, Eq)
data ExcerptNode = ExcerptNode (Maybe Int) (Either Excerpt [Int]) deriving (Show, Eq)

maybeIntListToExcerptNode :: [Maybe Int] -> ExcerptNode
maybeIntListToExcerptNode [] = ExcerptNode Nothing (Right [])
maybeIntListToExcerptNode (x:xs) = if all (==Nothing) xs
  then ExcerptNode x (Right [])
  else ExcerptNode x (Left $ Excerpt [ maybeIntListToExcerptNode xs ])

mergeExcerptNodes :: ExcerptNode -> ExcerptNode -> [ExcerptNode]
mergeExcerptNodes a b = mergeExcerptNodeIntoList a [b]

mergeExcerpts :: Excerpt -> Excerpt -> Excerpt
mergeExcerpts (Excerpt as) (Excerpt bs) = Excerpt $ foldr mergeExcerptNodeIntoList as bs

mergeExcerptNodeIntoList :: ExcerptNode -> [ExcerptNode] -> [ExcerptNode]
mergeExcerptNodeIntoList a [] = [a]
mergeExcerptNodeIntoList (ExcerptNode x u) (ExcerptNode y v : bs)
  | x == y = [ExcerptNode x (mergeBranches u v)]    bs
  where mergeBranches (Right xls) (Right yls) = Right . nub . sort $ xls    yls
        mergeBranches (Left xls)  (Right _)   = Left xls
        mergeBranches (Right _)   (Left yls)  = Left yls
        mergeBranches (Left xls)  (Left yls)  = Left $ mergeExcerpts xls yls
mergeExcerptNodeIntoList a (b:bs) = b : mergeExcerptNodeIntoList a bs

main :: IO ()
main = do
  let a = maybeIntListToExcerptNode [Nothing, Nothing, Just 0]
      b = maybeIntListToExcerptNode [Nothing, Nothing, Just 1]
      c = mergeExcerptNodes a b
  print c

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/528521.html

標籤：哈斯克尔

上一篇：使用三個串列的總和列印自定義字串

下一篇：typeclassbimap怎么沒有回圈定義