Đồ họa Rùa là một Haskell Monad

Question

Tôi đang cố gắng triển khai turtle graphics trong Haskell. Mục đích là để có thể viết một hàm như thế này:

draw_something = do 
    forward 100 
    right 90 
    forward 100 
    ... 

và sau đó có nó tạo ra một danh sách các điểm (có thể với những đặc tính bổ sung):

> draw_something (0,0) 0  -- start at (0,0) facing east (0 degrees) 
[(0,0), (0,100), (-100,100), ...] 

Tôi có tất cả làm việc này trong một 'bình thường', nhưng tôi đã thất bại trong việc thực hiện nó như một Haskell Monad và sử dụng ký hiệu. Các mã cơ bản:

data State a = State (a, a) a -- (x,y), angle 
    deriving (Show, Eq) 

initstate :: State Float 
initstate = State (0.0,0.0) 0.0 


-- constrain angles to 0 to 2*pi 
fmod :: Float -> Float 
fmod a 
    | a >= 2*pi = fmod (a-2*pi) 
    | a < 0 = fmod (a+2*pi) 
    | otherwise = a 

forward :: Float -> State Float -> [State Float] 
forward d (State (x,y) angle) = [State (x + d * (sin angle), y + d * (cos angle)) angle] 

right :: Float -> State Float -> [State Float] 
right d (State pos angle) = [State pos (fmod (angle+d))] 


bind :: [State a] -> (State a -> [State a]) -> [State a] 
bind xs f = xs ++ (f (head $ reverse xs)) 

ret :: State a -> [State a] 
ret x = [x] 

Với điều này bây giờ tôi có thể viết

> [initstate] `bind` (forward 100) `bind` (right (pi/2)) `bind` (forward 100) 
[State (0.0,0.0) 0.0,State (0.0,100.0) 0.0,State (0.0,100.0) 1.5707964,State (100.0,99.99999) 1.5707964] 

Và có được kết quả mong đợi. Tuy nhiên tôi không thể thực hiện trường hợp này là Monad.

instance Monad [State] where 
    ... 

kết quả trong

`State' is not applied to enough type arguments 
Expected kind `*', but `State' has kind `* -> *' 
In the instance declaration for `Monad [State]' 

Và nếu tôi quấn danh sách trong một đối tượng mới

data StateList a = StateList [State a] 

instance Monad StateList where 
    return x = StateList [x] 

tôi nhận được

Couldn't match type `a' with `State a' 
     `a' is a rigid type variable bound by 
     the type signature for return :: a -> StateList a 
      at logo.hs:38:9 
    In the expression: x   
    In the first argument of `StateList', namely `[x]' 
    In the expression: StateList [x] 

tôi đã cố gắng phiên bản khác nhau nhưng tôi không bao giờ làm cho nó chạy như tôi muốn. Tôi đang làm gì sai? Tôi hiểu gì không chính xác?

Answer 1

Đơn nguyên mà bạn đang nghĩ cần có hai thông số loại. Một cho đường mòn đã lưu (sẽ được sửa cho một chuỗi do cụ thể) và một cho các kết quả tính toán.

Bạn cũng cần phải suy nghĩ về cách soạn hai giá trị rùa-monadic để hoạt động liên kết là kết hợp. Ví dụ,

right 90 >> (right 90 >> forward 100) 

phải bằng

(right 90 >> right 90) >> forward 100 

(và dĩ nhiên là tương tự cho >>= vv). Điều này có nghĩa rằng nếu bạn đại diện cho lịch sử của rùa bằng một danh sách các điểm, hoạt động liên kết nhiều khả năng chỉ không thể nối thêm các danh sách các điểm lại với nhau; forward 100 một mình sẽ dẫn đến một cái gì đó như [(0,0),(100,0)] nhưng khi nó được thêm vào trước với luân phiên, các điểm đã lưu cần phải được xoay quá.

---

Tôi muốn nói rằng cách tiếp cận đơn giản nhất là sử dụng đơn lẻ Writer. Nhưng tôi sẽ không cứu được điểm, tôi sẽ chỉ cứu những hành động mà rùa thực hiện (để chúng ta không cần phải xoay các điểm khi kết hợp các giá trị). Một cái gì đó như

data Action = Rotate Double | Forward Double 

type TurtleMonad a = Writer [Action] a 

(Điều này cũng có nghĩa là chúng ta không cần phải theo dõi hướng hiện tại, nó chứa trong hành động.) Sau đó, mỗi người trong số các chức năng của bạn chỉ cần viết đối số của nó vào Writer.Và cuối cùng, bạn có thể trích xuất các danh sách cuối cùng từ nó và thực hiện một chức năng đơn giản có thể chuyển đổi tất cả các hành động vào một danh sách các điểm:

track :: [Action] -> [(Double,Double)] 

Cập nhật: Thay vì sử dụng [Action] nó sẽ là tốt hơn để sử dụng Seq từ Data.Sequence. Nó cũng là monoid và concatenating two sequences rất nhanh, độ phức tạp phân bổ là O (nhật ký (min (n1, n2))), so với O (n1) của (++). Vì vậy, loại được cải thiện sẽ là

type TurtleMonad a = Writer (Seq Action) a