Haskell - 在列表中相互比较不同的项目

haskell（或一般的函数式编程语言）的新手，所以我仍然很难将头脑中的逻辑转换为实际的代码。Haskell - 在列表中相互比较不同的项目

鉴于以下

data User = User String deriving (Eq, Show) 
data Task = Task String deriving (Eq, Show) 
data Command = 
    Add User 
    | Create Task 
    | Allow (User, Task) 
    deriving (Eq, Show)

我想确保每个允许有一个已添加的用户。上述逻辑将在验证:: [命令]功能被定义 - >布尔

example = [ 
    Add (User "Michael"), 
    Create (Task "Laundry"), 
    Allow (User "Michael", Task "Laundry") 
    ] 

Verified example -- Return True 

example2 = [ 
    Add (User "Michael"), 
    Create (Task "Laundry"), 
    Allow (User "Bob", Task "Laundry") 
    ] 

Verified example2 -- Return False

下面是我的思维过程，如果你能帮助我翻译成代码/完善我的想法，我真的很感激

颠倒命令列表。如果我看到允许使用用户和任务，那么它必须是真的，在列表中的某处，有一个具有该特定用户的添加。否则，返回false。
在Prelude中使用elem来查看命令中是否存在这样的Add（我在考虑递归）。

现在，我只能够成功地创建了一个简单的函数，扭转名单，

reverseList :: [Command] -> [Command] 
reverseList [] = [] 
reverseList (x:xs) = (reverse xs) ++ [x]

但除了我真的不知道从哪里开始实施验证:: [命令] - >布尔

编辑：刚刚发现Haskell有一个内置的反向功能，想我的reverseList不会被投入使用了

来源

2014-11-23 user3277633

注意，'reverseList（X：XS）=（反向XS）++ [X]'是一个相当坏主意（n^2复杂度）。 – Jubobs 2014-11-23 22:02:46

是啊，有趣的是，我只是阅读一篇关于如何实现逆向函数的糟糕方法的文章。不过我会使用内置的反转功能！ – user3277633 2014-11-23 22:06:44

我的理解是，命令列表表示依赖于每个先前命令的序列是有效的还是无效的。即[Add "Bob", Allow "Bob" ...]有效，而[Allow "Bob" ..., Add "Bob"]。

在这种情况下，最简单的方法是颠倒列表并遍历它;如果您发现Allow，请将其插入您必须找到的一组Add中;如果您发现Add，请将其从您必须找到的一组Add中删除。然后，一旦你到达空白列表，如果你的集合不是空的，你会发现命令序列无效。

您可以使用列表来表示集合，但使用Data.Set.Set会更容易，它已经定义了插入和删除（称为删除）函数。

下面是一些代码，让你开始：

import qualified Data.Set as S 

verify :: [Command] -> Bool 
verify = go S.empty . reverse where 

    go :: S.Set User -> [Command] -> Bool 
    go s [] = error "TODO" 
    go s (x:xs) = case x of 
        Create {} -> go s xs 
        Add u  -> error "TODO" 
        Allow (u, _) -> error "TODO"

你可以使用一个折，但使用原始递归编写它可能是有启发性。

对于这个工作，你需要也从中Ord为User：

newtype User = User String deriving (Eq, Show, Ord)

解决方案（PS给我扰流标签堆栈溢出）：

Scroll right >                                               go :: S.Set User -> [Command] -> Bool 
                                                     go s [] = S.null s 
                                                     go s (x:xs) = case x of 
                                                         Create {} -> go s xs 
                                                         Add u  -> go (S.delete u s) xs 
                                                         Allow (u, _) -> go (S.insert u s) xs

来源

2014-11-24 00:00:09 user2407038

奇怪的是，我可以编辑代码块并在编辑时正确预览，但检入浏览器的隐身窗口会告诉我编辑完成后扰动标记看起来不起作用。我可能会将此报告为meta的错误。 – bheklilr 2014-11-24 02:49:54

如何：

第一张进口reverse from Data.List：

import Data.List (reverse)

定义verify对命令列表的反向应用verifyBackwards：

verify :: [Command] -> Bool 
verify cmds = verifyBackwards (reverse cmds)

verifyBackwards然后将调用verifyElem每个元素与所述反转命令列表的其余部分一起（即在原始列表中该元素）and荷兰国际集团将结果与递归调用verifyBackwards之前的元素来验证其余元素：

verifyBackwards :: [Command] -> Bool 
verifyBackwards [] = True 
verifyBackwards (x:xs) = verifyElem x xs && verifyBackwards xs

最后verifyElem将返回True所有命令除Allow命令。对于Allow命令时，它会检查用户是Add ED是Allow ED之前：

verifyElem :: Command -> [Command] -> Bool 
verifyElem (Allow (User u, _)) xs = elem (Add (User u)) xs 
verifyElem _ _ = True

来源

2014-11-26 05:22:41

Haskell - 在列表中相互比较不同的项目

回答

相关问题