4

私は 10 年ぶりに Haskell を再学習しています。変更点を確認するためと、C#、SQL、JavaScript で過ごした日々への対策として、そして突然クールになったからです ;-)

ハノイの塔をコーディング カタとして設定することにしましたが、十分に単純なものですが、私のコードは慣用的ではないと既に感じており、Haskell のベテランが持っているかもしれないヒントやヒントを聞きたいと思っています。

型をもう少し面白くするために、問題を 2 つの部分に分割します。最初の部分である 関数movesは、パズルを解くために必要な一連の動きを生成します。コードの残りの部分は、タワーをモデル化し、移動を実行するように設計されています。

私が間違いなく不満を感じている部分の1つはmoveDisc機能です。これを4つのタワーに拡張するのは面倒です.

ハノイ.hs

module Hanoi 
where

import Data.Maybe

type Disc = Integer
type Towers = [[Disc]]
data Column = A | B | C deriving (Eq,Show)

getDisc :: Towers -> Column -> Maybe Disc
getDisc t A = listToMaybe $ t !! 0
getDisc t B = listToMaybe $ t !! 1
getDisc t C = listToMaybe $ t !! 2

validMove :: Towers -> Column -> Column -> Bool
validMove tower from to 
    | srcDisc == Nothing = False
    | destDisc == Nothing = True
    | otherwise = srcDisc < destDisc
    where srcDisc = getDisc tower from
          destDisc = getDisc tower to

moveDisc :: Towers -> Column -> Column -> Towers
moveDisc [a:as, b, c] A B = [as, a:b, c]
moveDisc [a:as, b, c] A C = [as, b, a:c]
moveDisc [a, b:bs, c] B A = [b:a, bs, c]
moveDisc [a, b:bs, c] B C = [a, bs, b:c]
moveDisc [a, b, c:cs] C A = [c:a, b, cs]
moveDisc [a, b, c:cs] C B = [a, c:b, cs]

moves :: Integer -> Column -> Column -> Column -> [(Column,Column)]
moves 1 a _ c = [(a,c)]
moves n a b c = moves (n-1) a c b ++ [(a,c)] ++ moves (n-1) b a c

solve :: Towers -> Towers
solve towers = foldl (\t (from,to) -> moveDisc t from to) towers (moves len A B C)
    where len = height towers

height :: Towers -> Integer
height (t:_) = toInteger $ length t

newGame :: Integer -> Towers
newGame n = [[1..n],[],[]]

TestHanoi.hs

module TestHanoi
where

import Test.HUnit
import Hanoi

main = runTestTT $ "Hanoi Tests" ~: TestList [

    getDisc [[1],[2],[2]] A ~?= Just 1 ,
    getDisc [[1],[2],[3]] B ~?= Just 2 ,
    getDisc [[1],[2],[3]] C ~?= Just 3 ,
    getDisc [[],[2],[3]] A ~?= Nothing ,
    getDisc [[1,2,3],[],[]] A ~?= Just 1 ,

    validMove [[1,2,3],[],[]] A B ~?= True ,
    validMove [[2,3],[1],[]] A B ~?= False ,
    validMove [[3],[],[1,2]] A C ~?= False ,
    validMove [[],[],[1,2,3]] A C ~?= False ,

    moveDisc [[1],[],[]] A B ~?= [[],[1],[]] ,
    moveDisc [[],[1],[]] B C ~?= [[],[],[1]] ,
    moveDisc [[1,2],[],[]] A B ~?= [[2],[1],[]] ,
    moveDisc [[],[2],[1]] C B ~?= [[],[1,2],[]] ,
    moveDisc [[1,2],[],[]] A C ~?= [[2],[],[1]] ,
    moveDisc [[3],[2],[1]] B A ~?= [[2,3],[],[1]] ,

    moves 1 A B C ~?= [(A,C)] ,
    moves 2 A B C ~?= [(A,B),(A,C),(B,C)] ,

    "acceptance test" ~: 
        solve [[1,2,3,4,5,6], [], []] ~?= [[],[],[1,2,3,4,5,6]] ,

    "is optimal" ~: 
        length (moves 3 A B C) ~?= 7
    ]

改善のためのコメントや提案をお待ちしております。

4

2 に答える 2

6

別の表現を使用した実装を次に示します。ペグ サイズの 3 つのリストを格納する代わりに、最初の要素が最小のディスクの位置に対応する列のリストを格納します。これには、行方不明のディスク、小さなディスクの上に大きなディスクが積み重ねられているなどの不正な状態を表すことが現在不可能であるという利点があります。また、多くの機能を実装するのが簡単になります。

ハノイ.hs

module Hanoi where

import Control.Applicative
import Control.Monad
import Data.List
import Data.Maybe

type Disc = Integer
type Towers = [Column]
data Column = A | B | C deriving (Eq, Show)

getDisc :: Column -> Towers -> Maybe Disc
getDisc c t = (+1) . toInteger <$> elemIndex c t

validMove :: Column -> Column -> Towers -> Bool
validMove from to = isJust . moveDisc from to

moveDisc :: Column -> Column -> Towers -> Maybe Towers
moveDisc from to = foldr check Nothing . tails
  where check (c:cs)
          | c == from   = const . Just $ to : cs
          | c == to     = const Nothing
          | otherwise   = fmap (c:)

moves :: Integer -> Column -> Column -> Column -> [(Column,Column)]
moves 1 a _ c = [(a,c)]
moves n a b c = moves (n-1) a c b ++ [(a,c)] ++ moves (n-1) b a c

solve :: Towers -> Towers
solve towers = fromJust $ foldM (\t (from,to) -> moveDisc from to t) towers (moves len A B C)
    where len = height towers

height :: Towers -> Integer
height = genericLength

newGame :: Integer -> Towers
newGame n = genericReplicate n A

ハノイTest.hs

module HanoiTest where

import Test.HUnit
import Hanoi

main = runTestTT $ "Hanoi Tests" ~: TestList [

    getDisc A [A, B, C] ~?= Just 1 ,
    getDisc B [A, B, C] ~?= Just 2 ,
    getDisc C [A, B, C] ~?= Just 3 ,
    getDisc A [B, B, C] ~?= Nothing ,
    getDisc A [A, A, A] ~?= Just 1 ,

    validMove A B [A, A, A] ~?= True ,
    validMove A B [B, A, A] ~?= False ,
    validMove A C [C, C, A] ~?= False ,
    validMove A C [C, C, C] ~?= False ,

    moveDisc A B [A] ~?= Just [B] ,
    moveDisc B C [B] ~?= Just [C] ,
    moveDisc A B [A, A] ~?= Just [B, A] ,
    moveDisc C B [C, B] ~?= Just [B, B] ,
    moveDisc A C [A, A] ~?= Just [C, A] ,
    moveDisc B A [C, B, A] ~?= Just [C, A, A] ,

    moves 1 A B C ~?= [(A,C)] ,
    moves 2 A B C ~?= [(A,B),(A,C),(B,C)] ,

    "acceptance test" ~: 
        solve [A, A, A, A, A, A] ~?= [C, C, C, C, C, C] ,

    "is optimal" ~: 
        length (moves 3 A B C) ~?= 7
    ]

表現の変更とは別に、無効な動きの場合にmoveDisc戻るようにすることで、合計も作成しました。そうすれば、それに関してNothing簡単に実装できます。validMoveただし、よりエレガントな実装方法があるように感じmoveDiscます。

solve引数が初期位置の場合にのみ機能することに注意してください。これはコードにも当てはまります ( の不完全なパターンが原因で失敗しますmoveDisc)。Nothingこの場合は戻ります。

編集:ランピオンの改善を追加moveDiscし、データ構造が最後になるように引数の順序を変更しました。

于 2011-05-04T23:56:06.963 に答える
1

Enum in Column を導出すると、moveDisk を書き直して任意の長さのリストを取得するのは簡単です。

(toInt a) < (toInt b)スイッチが(toInt a) - 1最初のタワーの最初で、次に2番目の下部、次に最初のaとbの間の距離、最初のconsの頭、2番目のコンス、そして残りの後の新しいタワーの場合を考えてみましょう。

于 2011-05-04T23:02:45.903 に答える