在我的Haskell代码中找不到错误 [英] Can't find the error in my Haskell code

问题描述

我试图将Scala的白菜-山羊-狼难题的一个(正在工作的！)解决方案转换为Haskell，但是在findSolutions中调用head时代码抛出并出错，因为解决方案列表为空，因此问题似乎在循环中. findMoves似乎工作正常.

I tried to translate a (working !) solution of the cabbage-goat-wolf puzzle from Scala to Haskell, but the code throws and error when calling head in findSolutions because the solution list is empty, so the problem seems to be somewhere in loop. findMoves seems to work fine.

import Data.Maybe(fromMaybe)

data Item = Farmer | Cabbage | Goat | Wolf deriving (Eq, Show)

type Position = ([Item], [Item]) 

validPos :: Position -> Bool
validPos p = valid (fst p) && valid (snd p) where   
   valid list = elem Farmer list || notElem Goat list || 
                (notElem Cabbage list && notElem Wolf list) 

findMoves :: Position -> [Position]
findMoves (left,right) = filter validPos moves where
    moves | elem Farmer left = map (\item -> (delItem item left, addItem item right)) left 
          | otherwise = map (\item -> (addItem item left, delItem item right)) right
    delItem item = filter (\i ->  notElem i [item, Farmer]) 
    addItem Farmer list = Farmer:list      
    addItem item list = Farmer:item:list      

findSolution :: Position -> Position -> [Position]
findSolution from to = head $ loop [[from]] where
    loop pps = do
          (p:ps) <- pps
          let moves = filter (\x -> notElem x (p:ps)) $ findMoves p
          if elem to moves then return $ reverse (to:p:ps)
                           else loop $ map (:p:ps) moves  

solve :: [Position]
solve = let all = [Farmer, Cabbage, Goat, Wolf]
        in findSolution (all,[]) ([],all)

当然，我也希望获得有关与实际错误无关的改进的提示.

Of course I would also appreciate hints concerning improvements not related to the actual error.

[更新]

仅作记录，我遵循了使用Set的建议.这是工作代码:

Just for the record, I followed the suggestion to use a Set. Here is the working code:

import Data.Set

data Item = Farmer | Cabbage | Goat | Wolf deriving (Eq, Ord, Show)

type Position = (Set Item, Set Item)

validPos :: Position -> Bool
validPos p = valid (fst p) && valid (snd p) where
   valid set = or [Farmer `member` set, Goat `notMember` set, 
                   Cabbage `notMember` set && Wolf `notMember` set]

findMoves :: Position -> [Position]
findMoves (left,right) = elems $ Data.Set.filter validPos moves where
    moves | Farmer `member` left = Data.Set.map (move delItem addItem) left
          | otherwise = Data.Set.map (move addItem delItem) right
    move f1 f2 item = (f1 item left, f2 item right)
    delItem item = delete Farmer . delete item 
    addItem item = insert Farmer . insert item 

findSolution :: Position -> Position -> [Position]
findSolution from to = head $ loop [[from]] where
    loop pps = do
          ps <- pps
          let moves = Prelude.filter (\x -> notElem x ps) $ findMoves $ head ps
          if to `elem` moves then return $ reverse $ to:ps
                             else loop $ fmap (:ps) moves

solve :: [Position]
solve = let all = fromList [Farmer, Cabbage, Goat, Wolf]
        in findSolution (all, empty) (empty, all)

可以更安全地调用findSolution中的head，并且应该使用一种更好的方法来打印解决方案，但除此之外，我对此感到非常满意.

The call to head in findSolution could be made safer, and a better way to print out the solution should be used, but apart from that I'm quite happy with it.

[更新2]

我认为以前的职位表述对于这种问题不是很理想.我切换到以下数据模型，该模型使移动等操作更加冗长，但很多更具可读性:

I think the former representations of the positions were suboptimal for this kind of problem. I switched to the following data model, which made moving etc slightly more verbose, but much more readable:

data Place = Here | There deriving (Eq, Show)

data Pos = Pos { cabbage :: Place
               , goat :: Place
               , wolf :: Place
               , farmer :: Place 
               } deriving (Eq, Show)

推荐答案

问题是[Farmer,Goat,Cabbage,Wolf]与[Farmer,Cabbage,Goat,Wolf]不同，并且在使用elem和notElem时不检查它.一种解决方案是始终对元素列表进行排序，例如在您可以使用的函数findMoves中:

The problem is that [Farmer,Goat,Cabbage,Wolf] is not the same that [Farmer,Cabbage,Goat,Wolf] and you don't check it when use elem and notElem. One solution is always sort the list of elements, e.g in the function findMoves you can use:

import Data.List(ord)
import Control.Arrow((***))

data Item = Farmer | Cabbage | Goat | Wolf deriving (Eq, Show, Ord)

findMoves (left,right) = map (sort***sort) $ filter validPos moves where
-- ....

solve = let all = sort [Farmer, Cabbage, Goat, Wolf]
-- ....

或者您可以使用一组Item而不是Item列表.

Or you can use a set of Item instead a list of Item.

这篇关于在我的Haskell代码中找不到错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！