私のHaskellコードでエラーを見つけることができません

Question

キャベツヤギオオカミパズルのソリューションをScalaからHaskellに翻訳しようとしましたが、をfindSolutionsにコールするとコードがスローされ、エラーが発生しますリストは空ですので、問題はループのどこかにあるようです。 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。

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

それとも、代わりに項目のリストを項目のセットを使用することができます。一つの解決策は、機能、使用することができますfindMovesで例えば、要素のリストを並べ替える常にあります。