在我的Haskell代碼中找不到錯誤

Question

我試圖翻譯一個從Scala到Haskell的捲心菜 - 山羊狼拼圖的解決方案，但由於解決方案在findSolutions中調用head時代碼會拋出並出錯列表是空的，所以問題似乎在循環中的某個地方。 findMoves似乎正常工作。

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) 

當然，我也希望提示有關與實際錯誤無關的改進。

[更新]

只是爲了記錄在案，我也跟着用Set的建議。這裏是工作代碼：

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調用可以作出更安全，更好的方式來打印出應該使用的解決方案，但除此之外，我與它很高興。

[更新2]

我覺得位置的前表示是次優的這樣那樣的問題。我切換到下面的數據模型，這讓移動等稍微詳細，但多更具可讀性：

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

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

Answer 1

的問題是，[Farmer,Goat,Cabbage,Wolf]是不一樣的那[Farmer,Cabbage,Goat,Wolf]，你不檢查的時候使用elem和notElem。一種解決方案總是排序元素，e.g列表中的函數findMoves你可以使用：

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] 
-- .... 

或者你也可以使用一組項目，而不是項目的列表。