하스켈 : 지퍼를위한 타입 클래스 만들기

Question

하스켈의 지퍼 패턴 (및 다른 기능 언어, 내가 생각하기에)을 트래버스하고 데이터 구조를 수정하는 방법에 대해 조금 읽었습니다. 그리고 이것이 좋은 것이라고 생각했습니다. 클래스는 날아가는 데이터 구조와 관계없이 코드를 작성하기 위해 공통적 인 순회 인터페이스를 제공 할 수 있기 때문에 Haskell에서 타입 클래스를 생성하는 데 필요한 기술을 연마 할 수있는 기회를 얻었습니다.

는 내가 아마 두 개의 클래스가 필요 거라고 생각 - 첫번째로 통과하는 루트 데이터 구조에 대해 하나, 그리고 을 만든 특수 데이터 구조를 :

module Zipper where 

class Zipper z where 
    go'up :: z -> Maybe z 
    go'down :: z -> Maybe z 
    go'left :: z -> Maybe z 
    go'right :: z -> Maybe z 

class Zippable t where 
    zipper :: (Zipper z) => t -> z 
    get :: (Zipper z) => z -> t 
    put :: (Zipper z) => z -> t -> z 

을하지만 몇 가지 간단한 이러한 시도 할 때

-- store a path through a list, with preceding elements stored in reverse 
data ListZipper a = ListZipper { preceding :: [a], following :: [a] } 

instance Zipper (ListZipper a) where 
    go'up ListZipper { preceding = [] } = Nothing 
    go'up ListZipper { preceding = a:ps, following = fs } = 
     Just $ ListZipper { preceding = ps, following = a:fs } 
    go'down ListZipper { following = [] } = Nothing 
    go'down ListZipper { preceding = ps, following = a:fs } = 
     Just $ ListZipper { preceding = a:ps, following = fs } 
    go'left _ = Nothing 
    go'right _ = Nothing 

instance Zippable ([a]) where 
    zipper as = ListZipper { preceding = [], following = as } 
    get = following 
    put z as = z { following = as } 

또는 이진 트리 :

-- binary tree that only stores values at the leaves 
data Tree a = Node { left'child :: Tree a, right'child :: Tree a } | Leaf a 
-- store a path down a Tree, with branches not taken stored in reverse 
data TreeZipper a = TreeZipper { branches :: [Either (Tree a) (Tree a)], subtree :: Tree a } 

instance Zipper (TreeZipper a) where 
    go'up TreeZipper { branches = [] } = Nothing 
    go'up TreeZipper { branches = (Left l):bs, subtree = r } = 
     Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } 
    go'up TreeZipper { branches = (Right r):bs, subtree = l } = 
     Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } 
    go'down TreeZipper { subtree = Leaf a } = Nothing 
    go'down TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } = 
     Just $ TreeZipper { branches = (Right r):bs, subtree = l } 
    go'left TreeZipper { branches = [] } = Nothing 
    go'left TreeZipper { branches = (Right r):bs } = Nothing 
    go'left TreeZipper { branches = (Left l):bs, subtree = r } = 
     Just $ TreeZipper { branches = (Right r):bs, subtree = l } 
    go'right TreeZipper { branches = [] } = Nothing 
    go'right TreeZipper { branches = (Left l):bs } = Nothing 
    go'right TreeZipper { branches = (Right r):bs, subtree = l } = 
     Just $ TreeZipper { branches = (Left l):bs, subtree = r } 

instance Zippable (Tree a) where 
    zipper t = TreeZipper { branches = [], subtree = t } 
    get TreeZipper { subtree = s } = s 
    put z s = z { subtree = s } 

목록과 같은 데이터 구조체

나는 그것이 컴파일 할 수 없었다, 난 그냥 내 Zippable 인스턴스 정의의 각각에 대해이 같은 오류를 많이 얻을 것 :

 
Zipper.hs:28:14: 
    Couldn't match expected type `z' 
      against inferred type `ListZipper a' 
     `z' is a rigid type variable bound by 
      the type signature for `zipper' at Zipper.hs:10:20 
    In the expression: ListZipper {preceding = [], following = as} 
    In the definition of `zipper': 
     zipper as = ListZipper {preceding = [], following = as} 
    In the definition for method `zipper' 

은 그래서 당장은 확실하지 않다. 내 문제는 선언을 사용하여 이 Zipper 일 때이 두 인스턴스를 함께 묶으려고한다는 것입니다.

Answer 1

(제외 :. 당신의 명명 체계는 ... 발명 하스켈 스타일은 일반적으로 낙타 표기법입니다.)

당신이 올바른 궤도에있어. 당신이 쓴 것은 다음과 같습니다.

{-# LANGUAGE RankNTypes #-} 
instance Zippable [a] where 
    zipper = ... :: forall z. (Zipper z) => [a] -> z 
    get = ... :: forall z. (Zipper z) => z -> [a] 
    set = ... :: forall z. (Zipper z) => z -> [a] -> z 

( Zipper z 주어진 모든 유형의 z의 경우는,하는 zipper :: [a] -> z이 존재한다.) 당신은 분명 너무 제한적이다, zipper = ... :: [a] -> ListZipper a을 정의 할 트링하고

.

코드는 다음과 같은 최소한의 변경으로 유형 체킹이됩니다

{-# LANGUAGE MultiParamTypeClasses #-} 
class (Zipper z) => Zippable z t where 
    zipper :: t -> z 
    get :: z -> t 
    set :: z -> t -> z 
instance Zippable (ListZipper a) [a] where 
    ... 
instance Zippable (TreeZipper a) (Tree a) where 
    ... 

이 multi-parameter type classes를 참조하십시오. 이것은 post-Haskell'98 확장이지만, 하스켈 구현은 그것을 광범위하게 지원합니다.

Answer 2

다중 매개 변수 유형 클래스 및 함수 종속성 대신 유형 동의어 계열을 사용할 수도 있습니다. 이와 같은 경우에는보다 명확하고 이해하기 쉬운 솔루션을 제공합니다. 이 경우 클래스와 인스턴스가 될 것입니다 :

class Zippable t where 
    type ZipperType t :: * 
    enter :: t -> ZipperType t 
    focus :: ZipperType t -> t 

instance Zippable [a] where 
    type ZipperType [a] = ListZipper a 
    enter = ... 
    focus = ... 

Fun with type functions 하스켈 익숙한 사람들을위한 동의어 가족을 입력 할 수있는 훌륭한 소개합니다. 나는 또한 이전에 기능적 종속성 대신 유형 동의어 패밀리를 자주 사용할 수있는 방법에 대해 an article을 작성했습니다.

희망이 도움이됩니다.