계산 구조 (Monads, Arrows 등)

Question

저는 하스켈에서 어떻게 계산이 모델링되었는지에 관심이 있습니다. 몇몇 자원은 모나드를 "계산 가능한 계산"으로, 화살표를 "추상적 인 계산보기"로 설명했습니다. 이런 방식으로 묘사 된 모노로이드 (monoid), 펑터 (functor) 또는 응용 펑터 (applicative functor)는 본 적이 없습니다. 그들은 필요한 구조가 부족한 것 같습니다.

나는 그 아이디어가 흥미롭고 비슷한 것을하는 다른 구조가 있는지 궁금해합니다. 그렇다면 내가 그들에게 익숙해지기 위해 사용할 수있는 자원은 무엇인가? 손쉬운 패키지가 Hackage에 있습니까?

참고 :이 질문은 Monads vs. Arrows 및 https://stackoverflow.com/questions/2395715/resources-for-learning-monads-functors-monoids-arrows-etc 유사하지만, 내가 funtors 넘어 구조, 실용적 펑, 모나드, 화살표를 찾고 있어요.

편집 : 나는 응용 펑터가 "계산 구조체"로 간주되어야한다고 인정하지만, 나는 아직 만나지 않은 것을 찾고있다. 여기에는 응용 펑터, 모나드 및 화살표가 포함됩니다.

Answer 1

Arrows은 범주별로 일반화되어 있으므로 Category typeclass입니다.

class Category f where 
    (.) :: f a b -> f b c -> f a c 
    id :: f a a 

Arrow typeclass 정의는 수퍼 클래스 Category있다. (haskell 감각의) 카테고리는 함수를 일반화 (당신이 그것들을 작성할 수는 있지만 적용 할 수는 없다)하며 따라서 "계산의 모델"이다. Arrow은 튜플을 사용하기위한 추가 구조로 Category을 제공합니다. 따라서 Category은 하스켈의 함수 공간에 대해 어떤 것을 비 춥니 다. Arrow은 제품 유형에 관한 내용으로 확장합니다.

모든 Monad은 "클레이 슬 카테고리 (Kleisli Category)"라고 불리는 것을 발생시키고이 구성은 ArrowApply의 인스턴스를 제공합니다. ArrowApply에서 Monad을 만들면 완전한 원이 행동을 바꾸지 않기 때문에 어떤 깊은 의미에서 Monad과 ArrowApply은 같은 것입니다.

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b } 

instance Monad m => Category (Kleisli m) where 
    id = Kleisli return 
    (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f) 

instance Monad m => Arrow (Kleisli m) where 
    arr f = Kleisli (return . f) 
    first (Kleisli f) = Kleisli (\ ~(b,d) -> f b >>= \c -> return (c,d)) 
    second (Kleisli f) = Kleisli (\ ~(d,b) -> f b >>= \c -> return (d,c)) 

사실 모든 Arrow는 Category 슈퍼 클래스에 추가 (종류 권리를 얻을 보편적으로 정량화)는 Applicative 상승을 제공, 그리고 적절한 Category 및 Applicative의 조합이 Arrow을 재구성하기에 충분하다 생각합니다.

이러한 구조는 깊이 연결되어 있습니다.

경고 : wishy-washy 해설 전방. 사고의 Functor/Applicative/Monad 방식과 사고의 Category/Arrow 방법 사이에 하나의 중앙 차이점은 Functor와 그 동류가 객체 (하스켈 타입)의 수준에서 일반화는 동안/ArrowCategory가의 generelazation 있다는 것입니다 도형 (하스켈의 함수)의 개념. 제 생각에 일반화 된 레벨 인 의 모폴로지에서 생각하는 것은 일반화 된 레벨 인 오브젝트에서 생각하는 것보다 높은 수준의 추상화가 필요하다는 것입니다. 때로는 좋은 일이지만 그렇지 않은 경우도 있습니다. 반면에, Arrows에는 범주 적 근거가 있고 수학에서 아무도 Applicative이 재미 있다고 생각하지만 은 일반적으로 Arrow보다 더 잘 이해됩니다.

기본적으로 당신이 생각할 수있는 "카테고리 < 화살표 < ArrowApply"와 "은 Functor < 실용적 < 모나드"등이 "종류 ~은 Functor", "화살표 ~ 실용적"와 "ArrowApply ~ 모나드".

더 아래 콘크리트 다음 "이중"또는 "공동 건설을 얻기 위해 범주 구조에서 (여기 morphisms을 의미) 하나는 종종"화살표 "의 방향을 반대로 할 수 있습니다 다른 구조 계산을 모델링 할로 ". 모나드가

class Functor m => Monad m where 
    return :: a -> m a 
    join :: m (m a) -> m a 

로 정의한다면, 는 다음 comonad이

class Functor m => Comonad m where 
    extract :: m a -> a -- this is co-return 
    duplicate :: m a -> m (m a) -- this is co-join 

이다 (좋아, 나는 하스켈 일을 정의하는 방법 아니라는 것을 알고 있지만, ma >>= f = join $ fmap f ma 및 join x = x >>= id 그래서 그냥뿐만 아니라 수)

이 문제는 꽤 일반적이기도합니다. Comonad은 셀룰러 오토 데이터의 기본적인 기본 구조입니다. completness, 나는 "확장 가능 펑"에 대한 펑과 Comonad 사이에 클래스의 에드워드 Kmett의 Control.Comonad 둔다는 duplicate 당신은 또한 그것은 모든 Monad들도

"확장 가능한"것으로 밝혀

extend :: (m a -> b) -> m a -> m b -- Looks familiar? this is just the dual of >>= 
    extend f = fmap f . duplicate 
    --this is enough 
    duplicate = extend id 

을 정의 할 수 있기 때문에 지적한다

monadDuplicate :: Monad m => m a -> m (m a) 
    monadDuplicate = return 

모든 Comonads이

comonadJoin :: Comonad m => m (m a) -> m a 
    comonadJoin = extract 

그래서 "결합 가능한"동안 이 구조들은 매우 가깝다.

Answer 2

모든 모나드는 화살표입니다 (모나드는 ArrowApply와 동형 임). 다른 방식으로, 모든 모나드는 이고 <*>은 Control.Monad.ap이고 *>은 >> 인 인스턴스입니다. 응용 프로그램이 >>= 작동을 보장하지 않기 때문에 응용 프로그램이 약합니다. 따라서 Applicative는 이전 결과를 검사하지 않고 값으로 분기하는 계산을 캡처합니다. 되돌아 보면 많은 모나 딕 코드가 실제로 적용 가능하며, 깨끗한 재 작성으로 이것이 일어날 것입니다.

GHC 7.4.1에서 최근 제한 유형을 사용하여 모나드를 확장하면 restricted monads에 대한 더 멋진 디자인이 가능할 수 있습니다. 그리고 parameterized monads을 보는 사람들도 있고, 물론 나는 Oleg에 의해 무언가에 대한 링크를 포함합니다.

Answer 3

라이브러리에서 이러한 구조는 다른 유형의 계산을 발생시킵니다.

예를 들어, 응용 프로그램을 정적 효과를 구현하는 데 사용할 수 있습니다. 그것으로 포핸드에 정의 된 효과를 의미합니다. 예를 들어 상태 시스템을 구현할 때 입력 상태를 거부하거나 수락합니다. 그것들은 그들의 입력 측면에서 내부 구조를 조작하는 데 사용할 수 없습니다.

유형 모두를 말한다 :

<*> :: f (a -> b) -> f a -> f b 

그것은 이유로 용이하고, (F)의 구조는 옴 (A)의 입력을 의존 할 수 없다. 왜냐하면 a는 타입 레벨에서 f에 도달 할 수 없기 때문입니다.

모나드는 동적 효과로 사용할 수 있습니다. 또한 유형 서명을 통해 추론 할 수 있습니다.

>>= :: m a -> (a -> m b) -> m b 

어떻게 볼 수 있습니까? 왜냐하면 a는 m과 같은 "수준"에 있기 때문입니다. 수학적으로 그것은 2 단계 과정입니다. Bind는 fmap과 join의 두 함수로 구성됩니다. 처음에 우리는 이전에 포함 된 새로운 구조를 만들 모나드 조치 fmap 함수 함께 사용

는

fmap :: (a -> b) -> m a -> m b 
f :: (a -> m b) 
m :: m a 
fmap f :: m a -> m (m b) 
fmap f m :: m (m b) 

fmap 함수는 입력 값에 따라, 새로운 구조를 만들 수 있습니다. 그리고 우리가 이렇게 우리가 입력에 의존하는 방식으로 모나드 연산 내에서 구조를 조작 할 수 있으며, 가입과 구조를 축소

join :: m (m a) -> m a 
join (fmap f m) :: m b 

많은 모나드가 함께 구현하기 쉽게 가입 :

(>>=) = join . fmap 

하지만 applicatives와

addCounter :: Int -> m Int() 

하지만 applicatives (및 모나드) 등의 작업을 수행 할 수 있습니다 :

이 모나드 가능합니다

addOne :: m Int() 

화살표는 입력 및 출력 유형에 대해 더 많은 제어권을 제공하지만 나에게는 실제로 적용 가능성과 유사하다고 느낍니다. 어쩌면 나는 그것에 대해 틀렸다.