Monad (기능적 프로그래밍) - Monad (functional programming)

에서 함수형 프로그래밍 하는 모나드는 구조화 프로그램을 허용하는 추상화 일반적으로는 . 지원 언어는 모나드를 사용 하여 프로그램 로직에 필요한 상용구 코드 를 추상화 할 수 있습니다 . 모나드 자신 제공하여이를 데이터 유형 의 특정 형식이고, (모나드의 각 유형에 대한 특정 타입) 연산을 하나 개와 함께 프로 값 래핑 어느 (a 수득 모나드 내에 기본형 모나드 값 )과 다른 모나 딕 값을 출력 하는 함수구성 합니다 ( 모나 딕 함수 라고 함 ). [1]

이를 통해 모나드는 잠재적 인 정의되지 않은 값 ( Maybe모나드 사용) 처리 또는 값을 유연하고 잘 구성된 목록 ( List모나드 사용 ) 내에 유지하는 것과 같은 광범위한 문제를 단순화 할 수 있습니다 . 모나드를 사용하면 프로그래머는 복잡한 함수 시퀀스를 보조 데이터 관리, 제어 흐름 또는 부작용 을 추상화 하는 간결한 파이프 라인 으로 바꿀 수 있습니다 . [1] [2]

모나드의 개념과 용어는 원래 범주 이론 에서 비롯되었으며 , 여기서 모나드는 추가 구조를 가진 펑터정의됩니다 . [a] 1980 년대 말과 1990 년대 초에 시작된 연구에 따르면 모나드는 통합 된 기능적 모델 하에서 겉보기에 이질적인 컴퓨터 과학 문제를 가져올 수 있다는 사실이 밝혀졌습니다. 범주 이론은 또한 모나드 법칙 으로 알려진 몇 가지 공식적인 요구 사항을 제공하며 , 이는 모든 모나드에서 충족되어야하며 모나드 코드 확인 하는 데 사용할 수 있습니다 . [3] [4]

모나드 는 일종의 계산에 대해 의미론을 명시하기 때문에 편리한 언어 기능을 구현하는 데 사용할 수도 있습니다. Haskell 과 같은 일부 언어 는 일반 모나드 구조 및 공통 인스턴스 에 대한 핵심 라이브러리사전 빌드 된 정의를 제공 합니다. [1] [5]

개요

"모나드의 경우 M, 유형 M a값은 a모나드 컨텍스트 내에서 유형 값에 액세스 할 수 있음을 나타냅니다 ." -CA McCann [6]

모나드는 두 가지 작업과 함께 유형 생성자에 의해 정의됩니다 M.

  • return :: a -> M a(또한 유닛 타입의 값을 감싸는) a(A) 내로 모나드 값 유형 M a,
  • join :: M (M a) -> M a( 컴포지션 이라고도 함 ) 유형의 래핑 된 모나드 값을 유형 M (M a)의 단순 모나드 값으로 래핑 해제 합니다 M a.

타입 생성자 M더욱이 것으로 가정 제공하는, 즉 fmap :: (a -> b) -> M a -> M b동안 returnjoin자연 호환성 관계 아래에 명시한 만족한다.

실제로 모나드는 일반적으로 bind연산자를 통해 정의 되며 중위 표기법으로 작성됩니다 >>=.

  • bind :: M a -> (a -> M b) -> M b이것은 M a유형 M b의 모나드 함수가 주어지면 모나 딕 유형 모나 딕 유형 매핑합니다 a -> M b.

bind또는 하나를 제공 join하여 모나드를 정의하는 것은 엄격하게 동일합니다.

  • 매핑 a -> M b에 functorially M a -> M (M b)과 합류 M (M b)M b, 바인딩은 ma >>= f통해 회수된다 join (fmap f ma).
  • 역으로,시키는 a = M b, 신원은 매핑 a = M bM b그 있도록 join mmb로 복구 mmb >>= idID가 신원지도입니다.

용법

모나드는 연산자가 표현식을 함께 연결 하는 파이프 라인유사하게 프로그래머가 일련의 작업을 구성 할 수 있도록합니다 bind. 이러한 시퀀스는 명령형 언어의 동작을 자연스럽게 반영합니다. 여기서 각 코드 줄은 변수 선언과 할당을 통해 최종적으로 수정 된 실행 컨텍스트를 다음으로 전달하는 명령어입니다.

do예를 들어 Haskell 표기법을 사용하면 모나 딕 코드 블록을 다음과 같이 작성할 수 있습니다.

main  ::  IO  ()  main  =  do  name  <  -getLine  -getLine :: IO String  putStrLn  ( "Hi"  ++  name  ++  "!" )  -putStrLn :: String-> IO () 

에서 IO모나드, 상기 바인딩에 상당 getLine >>= (putStrLn . hi)여기서 hi name = "Hi " ++ name ++ "!". do코드 블록을 작성 하면 명령형 코드의 가독성을 빌릴 수 있습니다. bind그러나 사용하면 순수 함수 파이프 라인을 작성할 수 있습니다.

일련의 작업이 컴퓨터 과학에 대한 모나드의 가장 강력한 응용 프로그램 인 것처럼 보이지만 상태, 부작용 및 I / O 작업을 처리하는 데있어 개념은 훨씬 더 일반적이며 예를 들어 ListMaybe모나드에 의해 제공된 더 간단한 예제가 많이 있습니다. . 더 미묘한 Reader모나드 모든 기능 타입을 나타내는 s -> a공통 소스로부터 s다른 표준 예와 같은 많은 다른 모나드 대한 구조적 모델 StateIO.

목록 모나드

목록은 모나드의 첫 번째 예를 제공합니다. 따라서 추상적 인 정의에도 불구하고 모나드는 대부분의 프로그래밍 언어에 공통적 인 매우 간단한 데이터 유형으로 구현됩니다.

부착 [a] = List a형 요소 목록의 유형 나타내는 a부 및 조성물에 List의해 정의되는을 :

  • unit :: a -> [a]이 요소를 포함 하는 단일 목록 x을 유형 a할당합니다 [x].
  • join :: [[a]] -> [a]유형 목록을 병합 된 유형 목록 [[a]]으로 결합하여 유형 목록을 연결합니다 [a].

매우 단순하기 때문에 목록 모나드는 어떻게 든 보편적입니다. 연관 연산에 의해 구성을 기다리는 모든 용어 시퀀스를 나타낼 수 있습니다.

예를 들어 pipe : [b -> b] -> b -> b파이프 라인으로 표시되는 함수 목록을 구성하는 함수를 고려하십시오 . 중첩 된 목록을 생성 된 하위 프로세스에 대한 은유로 생각하면 결과 체인 ​​프로세스를 형성하는 두 가지 동등한 방법이 있습니다.

  • pipe . (map pipe) :: [[b -> b]] -> b -> b
  • pipe . join :: [[b -> b]] -> b -> b

이 등가가 반영 연관성 의을 (.): 괄호는 생략 될 수있다 (f . g) . h= f . (g . h)= f . g . h번 작곡 기능에 중요하지 않는 순서와. List모나드로 작업 하면이 속성을 완전히 인식하고 List(b -> b)중첩 된 목록이 모나드 구성에 의해 자연스럽게 감소되는 모나드 유형의 값만 처리하는 데 집중할 수 있습니다.

참고 산술 연산과 같은 것으로 sum :: [Num] -> Num하고 prod :: [Num] -> Num또한 상기 실시 예의 간단한 변형을 제공한다. 이 사실의 결과입니다 (Num, (+), 0), (Num, (*), 1)그리고 (b -> b, (.), id)모든 일반적인 예입니다 monoids 연관 조성 법이 정의 유닛을 가지고있다, 즉 공간. 모나드 자체가 모노 이드 개념의 추상화이기 때문에 이러한 단순한 구조를 염두에 두어야합니다. 그러나 난해 하더라도 모나드는 엔도 펑터 범주에서 모노 이드입니다.

List모나드 에 대한 또 다른 광범위한 해석은에서 선택한 값에 대해 가능한 결과의 모음으로 보는 대안 의 표현입니다 . 덜 자연 스럽지만 이는 연산자 에 대한 편리한 관점을 제공하여 요소 별 함수 응용 프로그램에서 얻은 목록을 간단히 결합합니다.[a]abind

  • bind :: [a] -> (a -> [b]) -> [b]

이 그림에서 프로세스 a는의 가능한 결과 목록의 단일 요소에 연결되며 b바인딩은의 가능한 값 목록에서 간단히 열거됩니다 a. 이 관점은 목록의 구조적 순서를 설정하고 놓치기 위해 더 적응 된 언어를 사용합니다. 그러나 모나드 연산을 이해하는 데 도움이 될 수 있습니다.

예를 들어 powerset주어진 목록의 모든 하위 목록을 반환 하는 다음 함수를 고려 하십시오.

powerset  ::  [ a ]  ->  [[ a ]]  powerset  []  =  [ [] ]  powerset  ( x : xs )  =  do  ys  <  -powerset  xs  -ys :: [a]  [ x : ys ,  ys ]  - -x를 넣거나 넣지 마십시오 

에 해당하는 do블록 구현 powerset (x:xs) = powerset xs >>= (\ys -> [x: ys, ys])은의 표현력을 보여줍니다 bind.

예 : 어쩌면

모나드로 프로그래밍에 동기를 부여하기 위해 빠른 의사 코드 예제가 있습니다. 정의되지 않은 값 또는 작업은 강력한 소프트웨어가 적절하게 준비하고 처리해야하는 특정 문제 중 하나입니다.

이 목표를 향한 첫 번째 단계 는 값을 어떤 유형의 값 ( 모든 유형이 될 수 있음) 또는 값이없는 것으로 표시 하는 옵션 유형 을 만드는 입니다. 새 유형이 호출 되고 해당 유형의 값은 유형 값을 포함 하거나 빈 값이 될 수 있습니다 . 정의되었지만 컨텍스트에서 사용되는 유형 의 값 이 호출 됩니다. 이는 변수가 정의 된 값을 전달하는 경우와 그렇지 않은 경우를 구분하여 혼동을 피하기 위해 수행됩니다.TTMaybe TTNothingXTMaybeJust X

데이터  어쩌면  T  =  그냥  T  또는  아무것도 

Maybe TT예외의 원인에 대한 정보는 전달하지 않지만 기본 제공 예외 처리를 사용 하여 유형 을 새 유형으로 랩핑하는 "래핑"유형으로 이해할 수 있습니다 .

다음 코드에서 접두사가 붙은 변수 m에는 Maybe T일부 유형에 대한 유형이 T있습니다. 예를 들어 변수 mx에 값이 포함 된 경우 이는입니다 Just x. 여기서 변수 x의 유형은 T입니다. λx → ...이며 익명 함수 파라미터와 x타입 추론 하고 는 IS 기능 조성물 연산자.

또 다른 개선 사항은 함수가 유형 이있는 간단한 검사 된 예외관리 하고 단계가 실패하면 단락 되고 반환 되지만 계산이 성공하면 주석없이 올바른 값을 반환하는 경우입니다.MaybeNothing

부가 기능 add개의 추가 할 때 정확히 않는, Maybe값, mxmy과 같이 정의 될 수있다 :

 추가  :  ( 어쩌면  ,  어쩌면  )   아마  번호  추가 ( MX , )  =  ...  경우  MX가  있다  아무것도  다음  ...  아무것도  다른  경우  내이  있다  아무것도  다음  ...  아무것도  다른  ...  그냥  ( X  +  Y를 )  end  if 

Maybe값을 사례별로 처리하는 함수를 작성하는 것은 지루할 수 있으며 더 많은 함수가 정의 될수록 더 많아 질 것입니다. 연쇄 단계로 동작 함께이를 해소하는 한 방법 및과 중위 연산자x >>= y, 심지어는 직관적 다음으로, 각 단계에서 (정의되지 않은) 결과 먹이 나타낼 수있다. 그러나 각 결과는 기술적으로 다른 함수에 삽입 되므로 연산자는 매개 변수에 대한 함수를 사용합니다. 마찬가지로 add이미 출력값의 유형을 지정하고, 그것을 유연 조작자 유지 기능을 허용 해치지 않을 것을 자신의 입력으로부터 출력 상이한 유형 :

 >> =  :  ( 아마도  T ,  T   어쩌면  U )   아마  U  ( MX  >> =  F )  =  ...  경우  MX는  것입니다  ( 그냥은  X )  다음  ...  F ( X )  - F 반환 정의 된 값은 아마 U 입력하지  다른  ...  아무것도  F 반환하지 값 -  엔드  경우를 

사용 >>=가능 하면 add이제 훨씬 더 간결한 것으로 재정의 할 수 있습니다.

 추가 ( MX , 내을 )  =  MX  >> =  λx  > -  (  >> =  λy  ->  그냥  ( X  +  Y )) 

이것은 더 간결하지만 약간의 추가 분석을 통해 훨씬 더 강력한 것을 알 수 있습니다. 하나 들어있는 유일한 역할 Just에 연극 add입니다도되고 같은 기본 값에 태그하는 Maybe값입니다. 래핑하여 기본 값에 대한 Just 작동 방식을 강조하기 eta위해 지금 호출되는 함수로 재정의 할 수도 있습니다 .

 eta  :  T   아마도  T  eta ( x )  =  Just  x 

큰 그림은이 두 가지 기능이 있다는 것입니다 >>=및이 eta단순화하도록 설계되었다 add, 그러나 명확의 특성에 의존하지 않는 add에서 어떤 방식으로, 단지 Maybe유형입니다. 실제로 이러한 함수는 Maybe기본 값의 유형에 관계없이 유형 의 모든 값과 함수에 적용 할 수 있습니다. 예를 들어, 다음은 동일한 함수를 사용하여 정의되지 않은 값을 자동화하는 (Kleene의) 삼항 논리간결한 NOT 연산자입니다 .

trinot  :  어쩌면  부울   어쩌면  부울  trinot ( MP )  =  MP  >> =  λp  ->  ( ETA   하지 )  페이지 

그것은 밝혀 Maybe과 함께, 유형 >>=eta모나드를 형성한다. 다른 모나드는 다른 논리 프로세스를 구현하고 일부는 추가 속성을 가질 수 있지만 모두이 예제의 기본 개요를 따르는 세 가지 유사한 구성 요소 (직접 또는 간접)를 갖습니다. [1] [7]

정의

위의 예에서 사용 된 함수형 프로그래밍에서 모나드에 대한 더 일반적인 정의는 실제로 범주 이론의 표준 정의가 아닌 Kleisli 트리플을 기반으로합니다 . 그러나 두 구조는 수학적으로 동등하므로 두 정의 모두 유효한 모나드를 생성합니다. 잘 정의 된 기본 유형 T , U가 주어지면 모나드는 세 부분으로 구성됩니다.

하지만 모나드의 자격을 완전히 갖추려면 다음 세 부분도 몇 가지 법칙을 준수해야합니다.

  • unitbind에 대한 왼쪽 ID 입니다 .
    unit(a) >>= λx → f(x) f(a)
  • unitbind에 대한 오른쪽 ID이기도합니다 .
    ma >>= λx → unit(x) ma
  • bind 는 본질적으로 연관 적입니다 . [e]
    ma >>= λx → (f(x) >>= λy → g(y)) (ma >>= λx → f(x)) >>= λy → g(y)[1]

수학적으로,이 방법은 둘 다 (착신 카테고리 야기 제공 모나드 Kleisli 카테고리 ) 모노 이드 진 연산자와 같은 모나드 조성물 (계산하기위한 값)에서 펑의 범주에서, 단위 ID로한다. [ 인용 필요 ]

용법

모나드 패턴의 가치는 단순히 코드를 압축하고 수학적 추론에 대한 링크를 제공하는 것 이상입니다. 개발자가 사용하는 언어 나 기본 프로그래밍 패러다임무엇이든 모나드 패턴을 따르면 순전히 기능적 프로그래밍 의 많은 이점을 얻을 수 있습니다 . 으로 reifying 계산의 특정 종류를, 모나드뿐만 아니라 캡슐화 그 계산 패턴의 지루한 세부 사항을, 그러나 그것은에 그렇게 선언 코드의 선명도를 향상 방법. 모나드 값은 계산 된 값뿐만 아니라 계산 된 효과를 명시 적으로 나타내 므로 참조 적으로 투명한 위치 에서 모나드 식을 해당 값으로 대체 할 수 있습니다., 순수 표현식과 매우 유사하므로 재 작성을 기반으로하는 많은 기술과 최적화가 가능합니다 . [4]

일반적으로 프로그래머는 바인드사용 하여 모나드 함수를 시퀀스로 연결합니다. 이로 인해 일부는 모나드를 "프로그래밍 가능한 세미콜론"으로 설명 합니다 . 이는 명령문을 구분하기 위해 세미콜론을 사용 하는 명령형 언어 수에 대한 참조 입니다. [1] [5] 그러나, 모나드는 실제로 계산을 주문하지 않는다는 점을 강조해야합니다. 핵심 기능으로 사용하는 언어에서도 더 간단한 기능 구성으로 프로그램 내 단계를 정렬 할 수 있습니다. 모나드의 일반적인 유틸리티는 오히려 프로그램의 구조를 단순화하고 추상화를 통해 관심사 분리를 개선 하는있습니다. [4] [9]

모나드 구조는 데코레이터 패턴대한 고유 한 수학적 컴파일 시간 변형으로 볼 수도 있습니다 . 일부 모나드는 함수에 액세스 할 수없는 추가 데이터를 전달할 수 있으며, 일부는 특정 조건에서만 함수를 호출하는 것과 같이 실행을 더 세밀하게 제어합니다. 애플리케이션 프로그래머가 도메인 로직구현할 수있게 하면서 상용구 코드를 사전 개발 된 모듈로 오프로드 할 수 있기 때문에 모나드는 측면 지향 프로그래밍을 위한 도구로 간주 될 수도 있습니다 . [10]

모나드의 또 다른 주목할만한 용도는 순전히 기능적인 코드에서 입력 / 출력 또는 변경 가능한 상태 와 같은 부작용을 분리하는 것 입니다. 순수한 기능적 언어조차도 특히 함수 구성과 CPS ( continuation-passing style )의 복잡한 혼합을 통해 모나드없이 이러한 "불순한"계산을 구현할 있습니다 . [2] 하지만 모나드를 사용하면이 스캐 폴딩의 대부분은 본질적으로 CPS 코드의 각 반복 패턴을 가져 와서 별개의 모나드로 묶음으로써 추상화 될 수 있습니다. [4]

언어가 기본적으로 모나드를 지원하지 않는 경우에도 종종 별 어려움없이 패턴을 구현할 수 있습니다. 범주 이론에서 프로그래밍 용어로 변환 할 때 모나드 구조는 일반적인 개념 이며 제한된 다형성에 대해 동등한 기능을 지원하는 모든 언어로 직접 정의 할 수 있습니다 . 기본 유형에 대해 작업하는 동안 운영 세부 사항에 대해 불가지론 성을 유지하는 개념의 기능은 강력하지만 모나드의 고유 한 기능과 엄격한 동작은 다른 개념과 구별됩니다. [11]

응용

특정 모나드에 대한 논의는 일반적으로 주어진 모나드가 특정 계산 형식을 나타내므로 좁은 구현 문제를 해결하는 데 초점을 맞 춥니 다. 하지만 어떤 상황에서는 애플리케이션이 핵심 로직 내에서 적절한 모나드를 사용하여 높은 수준의 목표를 달성 할 수도 있습니다.

다음은 디자인의 핵심에 모나드가있는 몇 가지 애플리케이션입니다.

역사

프로그래밍에서 "모나드"라는 용어는 실제로 순수하게 기능하는 경향이 있는 APLJ 프로그래밍 언어로 거슬러 올라갑니다 . 그러나 이러한 언어에서 "monad"는 하나의 매개 변수를 취하는 함수 (두 개의 매개 변수가 "dyad"인 함수 등)의 약칭 일뿐입니다. [17]

수학자 Roger Godement 는 1950 년대 후반에 처음으로 모나드의 개념을 공식화했습니다 ( "표준 구조"라고 함). 그러나 "모나드"라는 용어는 범주 이론가 인 Saunders Mac Lane 때문 입니다. [ 표창장 ] 하여 위에서 정의 된 형태 바인드 그러나 원래 수학자 1965에 설명 된 하인리히 Kleisli 임의 모나드가 특징으로 할 수 있다는 것을 증명하기 위해 adjunction 두 (공변) 사이 펑. [18]

1980 년대부터 컴퓨터 과학 커뮤니티에서 모나드 패턴에 대한 모호한 개념이 드러나기 시작했습니다. 프로그래밍 언어 연구원 인 Philip Wadler 에 따르면 , 컴퓨터 과학자 John C. Reynolds 는 1970 년대와 1980 년대 초에 연속 전달 스타일 의 가치 , 형식적 의미론의 풍부한 소스로서의 범주 이론 및 유형 의 가치에 대해 논의하면서 여러 측면을 예상했습니다 . 값과 계산의 차이. [4] 1990 년까지 활발히 디자인 된 연구 용어 인 Opal 도 효과적으로 모나 딕 방식의 I / O를 기반으로하였으나 당시에는 연결이 이루어지지 않았다. [19]

컴퓨터 과학자 Eugenio Moggi 는 1989 년 컨퍼런스 논문에서 [20] 범주 이론의 모나드를 함수형 프로그래밍에 명시 적으로 연결 한 최초의 사람으로 1991 년에보다 정제 된 저널 제출이 이어졌습니다. 초기 작업에서 여러 컴퓨터 과학자들은 람다 미적분 에 대한 의미를 제공하는 범주 이론 . Moggi의 핵심 통찰력은 실제 프로그램이 단순히 값에서 다른 값으로의 함수가 아니라 해당 값에 대한 계산 을 형성하는 변환이라는 것 입니다. 범주 이론 용어로 공식화되면 모나드가 이러한 계산을 나타내는 구조라는 결론으로 ​​이어집니다. [삼]

Philip Wadler와 Simon Peyton Jones를 포함하여 여러 다른 사람들이이 아이디어를 대중화하고 구축했으며 , 둘 다 Haskell의 사양에 참여했습니다. 특히 Haskell 은 더 유연한 모나 딕 인터페이스로 전환 할 때까지 v1.2까지 문제가있는 "지연 스트림"모델을 사용하여 지연 평가로 I / O를 조정했습니다 . [21] Haskell 커뮤니티는 계속해서 함수형 프로그래밍의 많은 문제에 모나드를 적용 할 것이며, Haskell과 함께 일하는 연구자들은 결국 모나드 패턴을 응용 펑터화살표를 포함한 더 넓은 구조의 계층 구조로 일반화했습니다 . [ 인용 필요 ]

처음에 모나드를 사용한 프로그래밍은 대부분 하스켈과 그 파생물에 국한되었지만 함수형 프로그래밍이 다른 패러다임에 영향을 미치면서 많은 언어가 모나드 패턴을 통합했습니다 (이름이 아니라면 정신적으로). 이제 공식은 Scheme , Perl , Python , Racket , Clojure , Scala , F # 에 존재하며 새로운 ML 표준 으로도 고려되었습니다 . [ 인용 필요 ]

분석

모나드 패턴의 한 가지 이점은 프로그램 논리에 수학적 정밀도를 부여하는 것입니다. 모나드 법칙을 사용하여 인스턴스의 유효성을 확인할 수있을뿐만 아니라 관련 구조 (펑터 등)의 기능을 하위 유형 지정을 통해 사용할 수 있습니다 .

모나드 법칙 확인

Maybe예제 로 돌아가서 그 구성 요소는 모나드를 구성하도록 선언되었지만 모나드 법칙을 충족한다는 증거는 제공되지 않았습니다.

이것은 Maybe일반 법칙의 한쪽에 세부 사항을 연결 한 다음 다른쪽에 도달하기 위해 대수적으로 평등 체인을 구축하여 수정할 수 있습니다 .

법칙 1 : eta (a) >> = f (x) ⇔ (Just a) >> = f (x) ⇔ f (a)
법칙 2 : ma >> = eta (x) ⇔ ma if ma is (Just a) then eta (a) ⇔ Just a else  or Nothing ⇔ Nothing end if if 
법칙 3 :  ( ma >> = f (x) ) >> = g (y) ⇔ ma >> = ( f (x) >> = g (y) )  if (ma >> = f (x))  (저스트 b) 다음  경우 MA가 있다 (다만 a)는 다음 g는 (메사추세츠 >> = f는 (X)가) (F (X) >>는 = g (Y))로  다른 아무것도 아무것도 단부 경우  단부 경우경우 MA가 있다 (Just a)  f (a)  (Just b) 다음 (g ∘ f) a else if ma  (Just a) 이고 f (a) 는 Nothing then Nothing그렇지 않으면  없다 

펑터 에서 파생

컴퓨터 과학에서는 드물지만 범주 이론을 직접 사용할 수 있습니다.이 이론은 모나드를 두 개의 추가 자연 변환이 있는 펑터로 정의합니다 . 따라서 시작하려면 구조체 에 펑터 자격을 부여하기 위해 이라는 고차 함수 (또는 "기능적") 가 필요합니다 .

map φ : (a → b) → (ma → mb)

이것은 항상 중요한 문제는 아니지만, 특히 모나드가 기존의 펑터에서 파생 된 경우, 모나드는 자동으로 맵을 상속받습니다 . (역사적인 이유로 map대신 fmapHaskell에서 호출 됩니다.)

모나드의 첫 번째 변환은 실제로 Kleisli 트리플 의 동일한 단위 이지만 구조의 계층 구조를 자세히 살펴보면 단위 가 모나드와 기본 펑터 사이의 중간 구조 응용 펑터를 특징 짓는 것으로 밝혀졌습니다 . 적용 적 맥락에서 단위 는 때때로 순수 라고 불리지 만 여전히 동일한 기능입니다. 이 구조에서 다른 점은 법 단위 가 충족해야한다는 것입니다. 바인드가 정의되지 않은 제약 조건은 측면에서 주어진 지도 대신 :

(unit ∘ φ) x ↔ ((map φ) ∘ unit) x[22]

응용 펑터에서 모나드로의 마지막 도약은 두 번째 변환 인 조인 함수 (범주 이론에서는 일반적으로 μ 라고하는 자연스러운 변환입니다 )와 함께 모나드의 중첩 된 응용 프로그램을 "평탄화"합니다.

join(mma) : M (M T) → M T

특성 함수로서 join 은 모나드 법칙에 대한 세 가지 변형을 충족해야합니다. [ 인용 필요 ]

join ∘ (map join) mmma ↔ (join ∘ join) mmma ↔ ma
join ∘ (map unit) ma ↔ (join ∘ unit) ma ↔ ma
join ∘ (map map φ) mma ↔ ((map φ) ∘ join) mma ↔ mb

개발자가 직접 모나드 또는 Kleisli 트리플을 정의하는지 여부에 관계없이 기본 구조는 동일하며 양식은 서로 쉽게 파생 될 수 있습니다.

(map φ) ma ↔ ma >>= (unit ∘ φ)
join(mma) ↔ mma >>= id
ma >>= f ↔ (join ∘ (map f)) ma[23]

또 다른 예 : 목록

복잡한 다중 광장과 큐브 루트 기능을 할 수있다 구성 그들이 여섯 번째 루트 기능을 생성 할 수 있도록. 입력과 출력의 유형을 제어하는 ​​구조와 다른 작업을 구성하는 구조는 함께 목록 모나드 입니다. [24]
총알 심볼 • 나타내고 바인드 오퍼레이터를 z는 복소수이고, 대괄호가 나타내는 배열 = 수단 '과 같이 정의된다 '
( f g ) ( z )  : =  append ( map ( f , g ( z )))  lift ( f )  =  f °  : =  unit f  =  f unit  sqrt ° ( z )  ==  append ( map ( unit , sqrt ( z ))) =  append ( map ( sqrt , unit( z )))  sxrt ( z )  =  ( cbrt ° • sqrt ° ) ( z )  ==  append ( map ( cbrt ° , sqrt ° ( z ))) 
[ 의심스러운 ]

목록 모나드 자연스럽게 간단한 펑에서 모나드를 유도하는 것이 편리 할 수있는 방법을 보여줍니다. 많은 언어에서 목록 구조는 몇 가지 기본 기능과 함께 미리 정의되어 있으므로 List형식 생성자와 추가 연산자 ( ++중위 표기법으로 표시됨)는 이미 여기에 제공된 것으로 간주됩니다.

목록에 일반 값을 포함하는 것도 대부분의 언어에서 간단합니다.

단위 (x) = [x] 

여기에서 리스트 이해력 으로 함수를 반복적으로 적용하는 것은 리스트를 전체 모나드로 바인드 하고 변환 하기위한 쉬운 선택처럼 보일 수 있습니다 . 이 접근 방식의 어려움은 bind가 모나 딕 함수를 기대 한다는 것입니다.이 경우 목록 자체를 출력합니다. 더 많은 기능이 적용됨에 따라 중첩 된 목록의 레이어가 누적되어 기본적인 이해 이상이 필요합니다.

그러나 전체 목록, 즉 map간단한 함수 를 적용하는 절차 는 간단합니다.

(맵 φ) xlist = [φ (x1), φ (x2), ..., φ (xn)] 

이제,이 두 절차는 이미 List응용 펑터로 승격 됩니다. 모나드로 완전히 자격을 갖추려면 반복 된 구조를 평면화 하기 위한 조인 의 올바른 개념 만 필요하지만 목록의 경우 값을 포함하는 내부 목록을 추가하기 위해 외부 목록을 풀어야합니다.

join (xlistlist) = join ([xlist1, xlist2, ..., xlistn]) = xlist1 ++ xlist2 ++ ... ++ xlistn 

결과 모나드는 목록 일뿐만 아니라 함수가 적용될 때 자동으로 크기가 조정되고 압축됩니다. bind 는 이제 수식만으로도 파생 된 다음 List모나드 함수 파이프 라인을 통해 값 을 공급하는 데 사용할 수 있습니다.

(xlist >> = f) = 조인 ∘ (맵 f) xlist 

이 모나 딕 목록에 대한 한 가지 응용 프로그램은 비 결정적 계산을 나타냅니다 . List알고리즘의 모든 실행 경로에 대한 결과를 보유한 다음 각 단계에서 자신을 압축하여 어떤 결과로 이어진 경로를 "잊어 버릴"수 있습니다 (결정론적이고 철저한 알고리즘과의 중요한 차이점). 또 다른 이점은 검사가 모나드에 포함될 수 있다는 것입니다. 파이프 라인에서 함수를 다시 작성할 필요없이 특정 경로를 첫 번째 실패 지점에서 투명하게 정리할 수 있습니다. [23]

List빛나는 두 번째 상황 다중 값 함수를 구성하는 입니다. 예를 들어, 숫자 n 번째 복 소근n 개의 고유 한 복소수를 산출해야 하지만 그 결과에서 또 다른 m 번째 근을 취하면 최종 m • n 값은 m • n 번째 근 의 출력과 동일해야 합니다. . List이 문제를 완전히 자동화하여 각 단계의 결과를 수학적으로 정확한 목록으로 압축합니다. [24]

기법

모나드는 단순히 프로그램 로직을 구성하는 것 이상의 흥미로운 기술에 대한 기회를 제공합니다. Monads는 유용한 구문 기능의 토대를 마련 할 수 있으며, 높은 수준의 수학적 특성을 통해 상당한 추상화를 가능하게합니다.

통사적인 설탕 do-notation

사용하지만 바인드 공개적으로 종종 의미가 있습니다, 많은 프로그래머는 (라는 구문을 모방 필수적 문을 선호 할 표기법 , 하스켈을 수행-표기법OCaml로 , 연산 식F 번호 , [25]이해를위한 에서 스칼라 ). 이것은 모나 딕 파이프 라인을 코드 블록 으로 위장하는 구문 적 설탕 일뿐입니다 . 그런 다음 컴파일러는 이러한 식을 기본 기능 코드로 조용히 변환합니다.

add함수를에서 MaybeHaskell로 번역하면 이 기능이 실제로 작동하는 것을 보여줄 수 있습니다. addHaskell 의 비 모나드 버전은 다음과 같습니다.

add  mx  my  =  case  mx  of  Nothing-  >  Nothing  Just  x-  >  case  my  of  Nothing-  >  Nothing  Just  y-  >  Just  ( x  +  y ) 

모나 딕 하스켈에서는 unitreturn 의 표준 이름이며 람다 식은 명시 적으로 처리해야하지만 이러한 기술을 사용하더라도 모나드는보다 명확한 정의를 제공합니다.Maybe

add  mx  my  =  mx  >> =  ( \ x-  >  my  >> =  ( \ y-  >  return  ( x  +  y ))) 

하지만 do-notation을 사용하면 매우 직관적 인 순서로 더 증류 할 수 있습니다.

추가  MX   =   X  <-  MX  Y  <-   수익  ( X  +  Y ) 

두 번째 예제는 Maybe완전히 다른 언어 인 F #에서 어떻게 사용될 수 있는지 보여줍니다 . 계산 표현식 None을 사용하여 정의되지 않은 피연산자 또는 0으로 나누기에 대해 반환하는 "안전한 나누기"함수는 다음과 같이 작성할 수 있습니다.

let  readNum  ()  =  let  s  =  Console . ReadLine ()  let  succ , v  =  Int32 . TryParse ( s )  if  ( succ )  then  Some ( v )  else  None  let  secure_div  =  maybe  {  let !  x  =  readNum ()  let !  y  =  readNum ()  if  ( y  = 0 )  then  None  else  return  ( x  /  y )  } 

빌드시 컴파일러는 내부적으로이 함수를보다 조밀 한 바인드 호출 체인으로 "당질 제거" 합니다.

아마도 . 지연 ( 재미  ()  ->  아마 . 바인드 ( readNum () ,  재미  X  ->  아마 . 바인드 ( readNum () ,  재미  y를  ->  경우  ( Y = 0 )  다음  없음  다른  어쩌면 . 반환 ( X  /  Y ))) ) 

마지막 예를 들어, 일반 모나드 법칙 자체도 do-notation으로 표현할 수 있습니다.

do  {  x  <  -return  v ;  f  x  }  ==  do  {  f  v  }  do  {  x  <  -m ;  return  x  }  ==  do  {  m  }  do  {  y  <  -do  {  x  <  -m ;  f  x  };  g  y  }  ==  do  {  x  <  -m ;  y  <  -f  x ;   y  } 

편리하지만 개발자는이 블록 스타일이 순전히 구문이며 외부 모나 딕 (또는 비 모나드 CPS) 식으로 대체 될 수 있음을 항상 기억해야합니다. bind사용 하여 모나 딕 파이프 라인을 표현하는 것은 여전히 ​​많은 경우에 더 명확 할 수 있으며, 일부 함수형 프로그래밍 옹호자들은 블록 스타일이 초보자가 명령형 프로그래밍에서 습관을 이어갈 수 있기 때문에 기본적으로 피해야하며 분명히 우월 할 때만 사용해야한다고 주장합니다. [26] [1]

일반 인터페이스

모든 모나드는 모나드 법칙을 충족하는 특정 구현이 필요하지만 언어 내의 다른 구조 또는 표준 관용구와의 관계와 같은 다른 측면은 모든 모나드에서 공유됩니다. 결과적으로 언어 또는 라이브러리는 함수 프로토 타입 , 하위 유형 관계 및 기타 일반적인 사실이 포함 된 일반 Monad인터페이스를 제공 할 수 있습니다 . 개발에 유리한 출발점을 제공하고 새로운 모나드가 (펑터와 같은) 수퍼 타입의 기능을 상속 받도록 보장하는 것 외에도 인터페이스에 대한 모나드의 디자인을 확인하면 품질 관리의 또 다른 계층이 추가됩니다. [ 인용 필요 ]

연산자

모나 딕 코드는 종종 연산자의 현명한 사용을 통해 훨씬 더 단순화 될 수 있습니다. 지도 기능은 임시 모나드 기능보다 더에서 작동하기 때문에 특히 도움이 될 수있다; 모나 딕 함수가 미리 정의 된 연산자와 유사하게 작동하는 한, 을 사용 하여 더 단순한 연산자를 모나 딕 연산자로 즉시 " 리프트 " 할 수 있습니다 . [f] 이 기법 add을 사용하면 Maybe예제 의 정의를 다음과 같이 추출 할 수 있습니다.

add (mx, my) =지도 (+) 

이 프로세스는 addfor Maybe뿐만 아니라 전체 Monad인터페이스에 대해 정의하여 한 단계 더 나아갈 수 있습니다. 이렇게하면 구조 인터페이스와 일치하고 자체 구현하는 모든 새 모나드 는 즉시 해제 된 버전 add상속합니다 . 필요한 함수에 대한 유일한 변경은 형식 서명을 일반화하는 것입니다.

add : (모나드 번호, 모나드 번호) → 모나드 번호 [27] 

분석에도 유용한 또 다른 모나드 연산자는 모나드 구성 ( >=>여기서는 중위로 표시됨)으로, 더 수학적 스타일로 모나드 함수를 연결할 수 있습니다.

(f> => g) x = (f (x) → mb) >> = g (y = b) 

이 연산자를 사용하면 모나드 법칙을 함수만으로 작성하여 연관성과 신원의 존재를 강조 할 수 있습니다.

(단위> => g) ↔ g (f> => 단위) ↔ f (f> => g)> => h ↔ f> => (g> => h) [1] 

변형

수학적 수준에서 일부 모나드는 특히 좋은 속성을 가지며 특정 문제에 고유하게 적합합니다.

추가 모나드

첨가제 모나드 부가 폐쇄 연관 이진 연산자 부여 모나드이다 mplus식별 요소 아래 mplus 라는 mzero . Maybe모나드는 함께 고려 될 수 첨가제 Nothing로서 mzero 과의 변형 OR 연산자로 mplus . List빈 목록 []mzero 로, 연결 연산자 ++mplus작동 하는 가산 모나드이기도합니다 .

직관적 mzero는 하부 형에서 값없이 모나드 래퍼를 나타내고 있지만,이 역할 이후 또한 "제로"(보다는 "하나") 간주 흡수바인드 반환 mzero를 모나드 함수에 결합 할 때마다. 이 속성은 양면이며 어떤 값이 모나 딕 제로 함수에 바인딩되면 bindmzero 도 반환 합니다 .

범주 이론적 용어에서 가산 모나드는 bind (모든 모나드 와 마찬가지로)를 사용하는 모나드 함수에 대한 모노 이드로 , mplus 를 통해 다시 모나드 값에 대해 자격부여 합니다. [28] [g]

무료 모나드

때로는 모나드의 일반적인 개요가 유용 할 수 있지만 단순한 패턴은 하나 또는 다른 모나드를 권장하지 않습니다. 이것은 자유 모나드 가 들어오는 곳입니다. 모나드 범주의 자유 객체 로서 모나드 법칙 자체를 넘어서는 특별한 제약없이 모나드 구조를 나타낼 수 있습니다. 자유 모노 이드가 평가없이 요소를 연결 하는 것처럼 , 자유 모나드는 마커로 계산을 연결하여 유형 시스템을 충족하도록 허용하지만 그렇지 않으면 더 깊은 의미 체계 자체를 부과하지 않습니다.

예를 들어, JustNothing마커를 통해 전적으로 작업 하면 Maybe모나드는 실제로 무료 모나드입니다. 반면에 List모나드는 무료 모나드가 아닙니다. 목록에 대한 추가의 구체적인 사실 ( append 와 같은 )을 정의에 가져 오기 때문 입니다. 마지막 예제는 unitbind에 대한 유형 마커 와 재귀 적 선형 유형 생성자를 사용하는 추상 무료 모나드입니다 .

newtype은 무료 F (T) = T 단위 또는 바인딩 (F, 자유 F (T)) 부 (X) = X 수량 MX >> = F = ...이 경우 MX는  단위 X  ... F (X)를 다른 ... 바인딩 (f, mx) end if 

그러나 무료 모나드 는이 예제와 같이 연결 목록에 제한 되지 않으며 tree 와 같은 다른 구조를 중심으로 구축 될 수 있습니다 .

의도적으로 무료 모나드를 사용하는 것은 처음에는 비실용적으로 보일 수 있지만 형식적 특성은 특히 구문 문제에 적합합니다. 자유 모나드는 구문과 유형을 추적하는 데 사용할 수 있으며 의미 체계는 나중에 남겨두고 결과적으로 파서와 인터프리터 에서 사용되는 것을 발견했습니다 . [29] 다른 예로서 제공 역시 더 동적으로 작동 문제점들을 적용한 iteratees을 언어 내의. [30]

코 모나드

추가 속성으로 모나드를 생성하는 것 외에도 주어진 모나드에 대해 comonad를 정의 할 수도 있습니다 . 개념적으로 모나드는 기본 값으로 구성된 계산을 나타내면 코 모나드는 값으로의 축소로 볼 수 있습니다. 어떤 의미에서 모나 딕 코드는 완전히 "압축 해제"될 수 없습니다. 일단 값이 모나드 내에서 래핑되면 부작용과 함께 거기에 격리 된 상태로 유지됩니다 (순수한 기능적 프로그래밍에서 좋은 점입니다). 하지만 때때로 문제는 코 모나드가 명시 적으로 모델링 할 수있는 상황 별 데이터를 소비하는 것입니다.

기술적으로, comonad는 모나드 범주 형 이중 입니다. 즉, 형식 시그니처의 방향이 반전 된 경우에만 동일한 필수 구성 요소가 있음을 의미합니다 . 바인드 중심 모나드 정의 에서 시작 하여 comonad는 다음으로 구성됩니다.

  • 상위 유형 WT 를 표시 하는 유형 생성자 W
  • 여기서 counit 이라고 불리는 unit 의 이중은 comonad 에서 기본 값을 추출합니다.
counit (wa) : WT → T 
  • 축소 함수의 체인 확장 하는 바인드 (로도 =>>표시됨) 의 반전 :
(wa = >> f) : (WU, WU → T) → WT [h] 

extendcounit 은 모나드 법칙의 이중을 충족해야합니다.

counit ∘ ( (wa = >> f) → wb ) ↔ f (wa) → b wa = >> counit ↔ wa wa ( (= >> f (wx = wa)) → wb (= >> g (wy = wb)) → wc )( wa (= >> f (wx = wa)) → wb ) (= >> g (wy = wb)) → wc

모나드와 유사하게 comonads는 이중 join을 사용하여 functor에서 파생 될 수도 있습니다 .

  • duplicate 는 이미 comonadic 값을 취하여 다른 comonadic 구조 레이어로 래핑합니다.
중복 (wa) : WT → W (WT) 

같은 작업을하는 동안 확장이 반전 그러나, comonad는 않습니다 하지 가에 역할 역 기능을, 그 결과, comonads가와 펑 여전히 지도 하지 cofunctors는 . duplicate , counitmap을 사용하는 대체 정의 는 자체 comonad 법칙도 준수해야합니다.

((맵 중복) ∘ 중복) wa ↔ (중복 ∘ 중복) wa ↔ wwwa ((맵 코 유닛) ∘ 중복) wa ↔ (공 유닛 ∘ 중복) wa ↔ wa ((맵 맵 φ) ∘ 중복) wa ↔ (중복 ∘ (지도 φ)) wa ↔ wwb 

그리고 모나드와 마찬가지로 두 가지 형식은 자동으로 변환 될 수 있습니다.

(맵 φ) wa ↔ wa = >> (φ ∘ counit) wx 중복 wa ↔ wa = >> wx 
wa = >> f (wx) ↔ ((맵 f) ∘ 중복) wa 

간단한 예는 입력 값 및 공유 환경 데이터를 기반으로 값을 출력 하는 Product comonad 입니다. 사실, Product코모 나는 Writer모나드 의 이중 일 뿐이며 사실상 모나드와 동일합니다 Reader(둘 다 아래에서 설명합니다). Product그리고 Reader에만있는 그들이 동의 서명 기능, 그리고 그들이 어떻게 포장 또는 값을 풀기에 의해 그 기능을 보완 다릅니다.

덜 사소한 예는 Stream comonad로 , 데이터 스트림 을 표현 하고 extend 를 사용하여 들어오는 신호에 필터를 연결 하는 데 사용할 수 있습니다 . 사실, 모나드만큼 인기가 없지만 연구원들은 특히 스트림 처리데이터 흐름 프로그래밍 모델링에 유용한 코 모나드를 발견했습니다 . [31] [32]

그러나 엄격한 정의로 인해 모나드와 코 모나드 사이에서 단순히 객체를 앞뒤로 이동할 수는 없습니다. 더 높은 추상화로서 화살표 는 두 구조를 모두 포함 할 수 있지만 모나드 코드와 코 모나드 코드를 결합하는보다 세분화 된 방법을 찾는 것은 활발한 연구 분야입니다. [33] [34]

더 많은 예

Identity 모나드

가장 간단한 모나드는 Identity 모나드로 , 모나드 법칙을 충족시키기 위해 일반 값과 ​​함수에 주석을 추가합니다.

새로운 유형 ID T = T 단위 (x) = x (x >> = f) = f (x)

Identity재귀 모나드 변환기에 대한 기본 케이스제공하는 것과 같이 실제로 유효한 용도가 있습니다 . 또한 명령형 블록 내에서 기본 변수 할당을 수행하는 데 사용할 수도 있습니다. [i] [ 인용 필요 ]

컬렉션

적절한 추가있는 모든 컬렉션 은 이미 무료 모노 이드이지만 잘 정의 된 조인이 있고 모나드 자격을 갖춘 List유일한 컬렉션 은 아닙니다 . 추가에 특별한 속성을 부여하여 다른 모나드 컬렉션으로 변형시킬 수도 있습니다 . [j] [ citation needed ]List

수집 모노 이드 속성
명부 비어 있는
유한 멀티 세트 교환
유한 세트 교환 및 멱등
유한 순열 비 교환 및 멱등

IO 모나드 (Haskell)

이미 언급했듯이 순수 코드에는 관리되지 않는 부작용이 있어서는 안되지만 프로그램이 효과 명시 적으로 설명하고 관리하는 것을 배제하지는 않습니다 . 이 아이디어는 Haskell의 IO 모나드 의 핵심 입니다. 유형의 객체 IO a는 프로그램 외부 세계의 현재 상태를 포함하고 type 값을 계산하는 것으로 볼 수 있습니다 a. 값을 계산하지 않는 계산 (즉, 프로 시저) IO ()은 더미 값을 "계산"하는 유형을 갖습니다 (). 프로그래머가 IO값을 함수에 바인딩하면 함수는 해당 세계관 (사용자, 파일 등의 입력)에 따라 결정을 내린 다음 새로운 세계 상태 (프로그램 출력)를 반영하는 모나 딕 값을 생성합니다. [21]

예를 들어, Haskell에는 파일이 있는지 확인하는 기능과 파일을 삭제하는 기능을 포함 하여 더 넓은 파일 시스템 에서 작동하는 여러 기능 이 있습니다. 두 가지 유형의 서명은 다음과 같습니다.

doesFileExist  ::  FilePath-  >  IO  Bool  removeFile  ::  FilePath-  >  IO  () 

첫 번째는 주어진 파일이 실제로 존재하는지 여부에 관심이 있으며 결과적으로 모나드 내에서 부울 값을 출력합니다 IO. 반면에 두 번째 함수는 파일 시스템에서 작동하는 것과 관련이 있으므로 IO출력 하는 컨테이너가 비어 있습니다.

IO그러나 파일 I / O에만 국한되지 않습니다. 사용자 I / O도 허용하고 명령형 구문 설탕과 함께 일반적인 "Hello, World!"를 모방 할 수 있습니다 . 프로그램 :

main  ::  IO  ()  main  =  do  putStrLn  "Hello, world!"  putStrLn  "사용자 이름이 무엇입니까?"  name  <  -getLine  putStrLn  ( "만나서 반갑습니다,"  ++  name  ++  "!" ) 

Desugared는 다음과 같은 모나드 파이프 라인으로 변환됩니다 ( >>Haskell 에서는 모나 딕 효과 만 중요하고 기본 결과를 버릴 수있는 경우에만 bind 의 변형입니다 ).

main  ::  IO  ()  main  =  putStrLn  "Hello, world!"  >>  putStrLn  "사용자 이름이 무엇입니까?"  >>  의 getline  >> =  ( \ 이름  ->  putStrLn  ( "니스 만나서"  ++  이름을  ++  "!" )) 

작성자 모나드 (JavaScript)

또 다른 일반적인 상황은 로그 파일을 보관 하거나 프로그램의 진행 상황을보고하는 것입니다. 때로는 프로그래머가 나중에 프로파일 링 하거나 디버깅 하기 위해 더 구체적인 기술 데이터를 기록하려고 할 수 있습니다 . 라이터 모나드 단계별 축적 보조 출력을 생성함으로써 이러한 작업을 처리 할 수있다.

모나드 패턴이 주로 기능적인 언어로 제한되지 않는 방법을 보여주기 위해이 예제 WriterJavaScript 에서 모나드 를 구현합니다 . 첫째, 배열 (중첩 된 꼬리 포함)을 사용하면 Writer유형을 연결된 목록 으로 구성 할 수 있습니다 . 기본 출력 값은 배열의 위치 0에 있으며 위치 1은 암시 적으로 보조 음의 체인을 보유합니다.

const  writer  =  [ value ,  []]; 

단위 정의 도 매우 간단합니다.

const  단위  =   =>  [ ,  []]; 

디버깅 노트와 함께 객체 를 출력하는 간단한 함수를 정의하려면 단위필요 Writer합니다.

const squared = x => [x * x, [`${x} was squared.`]]; const halved = x => [x / 2, [`${x} was halved.`]]; 

A true monad still requires bind, but for Writer, this amounts simply to appending a function's output to the monad's linked list:

const bind = (writer, transform) => { const [value, log] = writer; const [result, updates] = transform(value); return [result, log.concat(updates)]; }; 

The sample functions can now be chained together using bind, but defining a version of monadic composition (called pipelog here) allows applying these functions even more succinctly:

const pipelog = (writer, ...transforms) => transforms.reduce(bind, writer); 

The final result is a clean separation of concerns between stepping through computations and logging them to audit later:

pipelog(unit(4), squared, halved); // Resulting writer object = [8, ['4 was squared.', '16 was halved.']] 

Environment monad

An environment monad (also called a reader monad and a function monad) allows a computation to depend on values from a shared environment. The monad type constructor maps a type T to functions of type ET, where E is the type of the shared environment. The monad functions are:

The following monadic operations are useful:

The ask operation is used to retrieve the current context, while local executes a computation in a modified subcontext. As in a state monad, computations in the environment monad may be invoked by simply providing an environment value and applying it to an instance of the monad.

Formally, a value in an environment monad is equivalent to a function with an additional, anonymous argument; return and bind are equivalent to the K and S combinators, respectively, in the SKI combinator calculus.

State monads

A state monad allows a programmer to attach state information of any type to a calculation. Given any value type, the corresponding type in the state monad is a function which accepts a state, then outputs a new state (of type s) along with a return value (of type t). This is similar to an environment monad, except that it also returns a new state, and thus allows modeling a mutable environment.

type State s t = s -> (t, s) 

Note that this monad takes a type parameter, the type of the state information. The monad operations are defined as follows:

-- "return" produces the given value without changing the state. return x = \s -> (x, s) -- "bind" modifies m so that it applies f to its result. m >>= f = \r -> let (x, s) = m r in (f x) s 

Useful state operations include:

get = \s -> (s, s) -- Examine the state at this point in the computation. put s = \_ -> ((), s) -- Replace the state. modify f = \s -> ((), f s) -- Update the state 

Another operation applies a state monad to a given initial state:

runState :: State s a -> s -> (a, s) runState t s = t s 

do-blocks in a state monad are sequences of operations that can examine and update the state data.

Informally, a state monad of state type S maps the type of return values T into functions of type , where S is the underlying state. The return and bind function are:

.

From the category theory point of view, a state monad is derived from the adjunction between the product functor and the exponential functor, which exists in any cartesian closed category by definition.

Continuation monad

A continuation monad with return type R maps type T into functions of type . It is used to model continuation-passing style. The return and bind functions are as follows:

The call-with-current-continuation function is defined as follows:

Program logging

The following code is pseudocode. Suppose we have two functions foo and bar, with types

foo : int -> int bar : int -> int 

That is, both functions take in an integer and return another integer. Then we can apply the functions in succession like so:

foo (bar x) 

Where the result is the result of foo applied to the result of bar applied to x.

But suppose we are debugging our program, and we would like to add logging messages to foo and bar. So we change the types as so:

foo : int -> int * string bar : int -> int * string 

So that both functions return a tuple, with the result of the application as the integer, and a logging message with information about the applied function and all the previously applied functions as the string.

Unfortunately, this means we can no longer compose foo and bar, as their input type int is not compatible with their output type int * string. And although we can again gain composablility by modifying the types of each function to be int * string -> int * string, this would require us to add boilerplate code to each function to extract the integer from the tuple, which would get tedious as the number of such functions increases.

Instead, let us define a helper function to abstract away this boilerplate for us:

bind : int * string -> (int -> int * string) -> int * string 

bind takes in an integer and string tuple, then takes in a function (like foo) that maps from an integer to an integer and string tuple. Its output is an integer and string tuple, which is the result of applying the input function to the integer within the input integer and string tuple. In this way, we only need to write boilerplate code to extract the integer from the tuple once, in bind.

Now we have regained some composability. For example:

bind (bind (x,s) bar) foo 

Where (x,s) is an integer and string tuple.

To make the benefits even clearer, let us define an infix operator as an alias for bind:

(>>=) : int * string -> (int -> int * string) -> int * string 

So that t >>= f is the same as bind t f.

Then the above example becomes:

((x,s) >>= bar) >>= foo 

Finally, it would be nice to not have to write (x, "") every time we wish to create an empty logging message, where "" is the empty string. So let us define a new function:

return : int -> int * string 

Which wraps x in the tuple described above.

Now we have a nice pipeline for logging messages:

((return x) >>= bar) >>= foo 

That allows us to more easily log the effects of bar and foo on x.

int * string is analogous to a monadic value. bind and return are analogous to the corresponding functions of the same name. In fact, int * string, bind, and return form a monad.

See also

Alternatives for modeling computations:

  • Effect systems are a different way to describe side effects as types
  • Uniqueness types are a third approach to handling side-effects in functional languages

Related design concepts:

  • Aspect-oriented programming emphasizes separating out ancillary bookkeeping code to improve modularity and simplicity
  • Inversion of control is the abstract principle of calling specific functions from an overarching framework
  • Type classes are a specific language feature used to implement monads and other structures in Haskell
  • The decorator pattern is a more concrete, ad-hoc way to achieve similar benefits in object-oriented programming

Generalizations of monads:

  • Applicative functors generalize from monads by keeping only unit and laws relating it to map
  • Arrows use additional structure to bring plain functions and monads under a single interface
  • Monad transformers act on distinct monads to combine them modularly

Notes

  1. ^ Due to the fact that functions on multiple free variables are common in programming, monads as described in this article are technically what category theorists would call strong monads.[3]
  2. ^ Semantically, M is not trivial and represents an endofunctor over the category of all well-typed values:
  3. ^ While a (parametrically polymorphic) function in programming terms, unit (often called η in category theory) is mathematically a natural transformation, which maps between functors:
  4. ^ bind, on the other hand, is not a natural transformation in category theory, but rather an extension that lifts a mapping (from values to computations) into a morphism between computations:
  5. ^ Strictly speaking, bind may not be formally associative in all contexts because it corresponds to application within lambda calculus, not mathematics. In rigorous lambda-calculus, evaluating a bind may require first wrapping the right term (when binding two monadic values) or the bind itself (between two monadic functions) in an anonymous function to still accept input from the left.[8]
  6. ^ Some languages like Haskell even provide a pseudonym for map in other contexts called lift, along with multiple versions for different parameter counts, a detail ignored here.
  7. ^ Algebraically, the relationship between the two (non-commutative) monoid aspects resembles that of a near-semiring, and some additive monads do qualify as such. However, not all additive monads meet the distributive laws of even a near-semiring.[28]
  8. ^ In Haskell, extend is actually defined with the inputs swapped, but as currying is not used in this article, it is defined here as the exact dual of bind.
  9. ^ In category theory, the Identity monad can also be viewed as emerging from adjunction of any functor with its inverse.
  10. ^ Category theory views these collection monads as adjunctions between the free functor and different functors from the category of sets to the category of monoids.

References

  1. ^ a b c d e f g h O'Sullivan, Bryan; Goerzen, John; Stewart, Don (2009). "Monads". Real World Haskell. Sebastopol, California: O'Reilly Media. chapter 14. ISBN 978-0596514983.
  2. ^ a b Wadler, Philip (June 1990). Comprehending Monads. ACM Conference on LISP and Functional Programming. Nice, France. CiteSeerX 10.1.1.33.5381.
  3. ^ a b c Moggi, Eugenio (1991). "Notions of computation and monads" (PDF). Information and Computation. 93 (1): 55–92. CiteSeerX 10.1.1.158.5275. doi:10.1016/0890-5401(91)90052-4.
  4. ^ a b c d e Wadler, Philip (January 1992). The essence of functional programming. 19th Annual ACM Symposium on Principles of Programming Languages. Albuquerque, New Mexico. CiteSeerX 10.1.1.38.9516.
  5. ^ a b Hudak, Paul; Peterson, John; Fasel, Joseph (1999). "About Monads". A Gentle Introduction to Haskell 98. chapter 9.
  6. ^ C. A. McCann's answer (Jul 23 '10 at 23:39) How and why does the Haskell Cont monad work?
  7. ^ Spivey, Mike (1990). "A functional theory of exceptions" (PDF). Science of Computer Programming. 14 (1): 25–42. doi:10.1016/0167-6423(90)90056-J.
  8. ^ "Monad laws". HaskellWiki. haskell.org. Retrieved 14 October 2018.
  9. ^ "What a Monad is not". 7 October 2018.
  10. ^ De Meuter, Wolfgang (1997). Monads as a theoretical foundation for AOP (PDF). International Workshop on Aspect Oriented Programming at ECOOP. Jyväskylä, Finland. CiteSeerX 10.1.1.25.8262.
  11. ^ "Monad (sans metaphors)". HaskellWiki. 1 November 2009. Retrieved 24 October 2018.
  12. ^ O'Sullivan, Bryan; Goerzen, John; Stewart, Don (2009). "Using Parsec". Real World Haskell. Sebastopol, California: O'Reilly Media. chapter 16. ISBN 978-0596514983.
  13. ^ Stewart, Don (17 May 2007). "Roll Your Own Window Manager: Tracking Focus with a Zipper". Control.Monad.Writer. Archived from the original on 20 February 2018. Retrieved 19 November 2018.
  14. ^ Benton, Nick (2015). "Categorical Monads and Computer Programming" (PDF). London Mathematical Society Impact150 Stories. 1. Retrieved 19 November 2018.
  15. ^ Kiselyov, Olag (2007). "Delimited Continuations in Operating Systems". Modeling and Using Context. Springer Berlin Heidelberg. pages 291--302. ISBN 978-3-540-74255-5.
  16. ^ Meijer, Erik (27 March 2012). "Your Mouse is a Database". ACM Queue. 10 (3). Retrieved 19 November 2018.
  17. ^ Iverson, Kenneth (September 1987). "A dictionary of APL". APL Quote Quad. 18 (1): 5–40. doi:10.1145/36983.36984. ISSN 1088-6826. Retrieved 19 November 2018.
  18. ^ Kleisli, Heinrich (1965). "Every standard construction is induced by a pair of adjoint functors" (PDF). Proceedings of the American Mathematical Society. 16 (3): 544–546. doi:10.1090/S0002-9939-1965-0177024-4. Retrieved 19 November 2018.
  19. ^ Peter Pepper, ed. (November 1997). The Programming Language Opal (Technical report) (5th corrected ed.). Fachbereich Informatik, Technische Universität Berlin. CiteSeerX 10.1.1.40.2748.
  20. ^ Moggi, Eugenio (June 1989). Computational lambda-calculus and monads (PDF). Fourth Annual Symposium on Logic in computer science. Pacific Grove, California. CiteSeerX 10.1.1.26.2787.
  21. ^ a b Peyton Jones, Simon L.; Wadler, Philip (January 1993). Imperative functional programming (PDF). 20th Annual ACM Symposium on Principles of Programming Languages. Charleston, South Carolina. CiteSeerX 10.1.1.53.2504.
  22. ^ "Applicative functor". HaskellWiki. Haskell.org. 7 May 2018. Archived from the original on 30 October 2018. Retrieved 20 November 2018.
  23. ^ a b Gibbard, Cale (30 December 2011). "Monads as containers". HaskellWiki. Haskell.org. Archived from the original on 14 December 2017. Retrieved 20 November 2018.
  24. ^ a b Piponi, Dan (7 August 2006). "You Could Have Invented Monads! (And Maybe You Already Have.)". A Neighborhood of Infinity. Archived from the original on 24 October 2018. Retrieved 16 October 2018.
  25. ^ "Some Details on F# Computation Expressions". Retrieved 9 October 2018.
  26. ^ "Do notation considered harmful". HaskellWiki. Retrieved 12 October 2018.
  27. ^ Giles, Brett (12 August 2013). "Lifting". HaskellWiki. Haskell.org. Archived from the original on 29 January 2018. Retrieved 25 November 2018.
  28. ^ a b Rivas, Exequiel; Jaskelioff, Mauro; Schrijvers, Tom (July 2015). From monoids to near-semirings: the essence of MonadPlus and Alternative (PDF). 17th International ACM Symposium on Principles and Practice of Declarative Programming. Siena, Italy. CiteSeerX 10.1.1.703.342.
  29. ^ Swierstra, Wouter (2008). "Data types à la carte" (PDF). Functional Pearl. Journal of Functional Programming. Cambridge University Press. 18 (4): 423–436. CiteSeerX 10.1.1.101.4131. doi:10.1017/s0956796808006758. ISSN 1469-7653.
  30. ^ Kiselyov, Oleg (May 2012). Schrijvers, Tom; Thiemann, Peter (eds.). Iteratees (PDF). International Symposium on Functional and Logic Programming. Lecture Notes in Computer Science. 7294. Kobe, Japan: Springer-Verlag. pp. 166–181. doi:10.1007/978-3-642-29822-6_15. ISBN 978-3-642-29822-6.
  31. ^ Uustalu, Tarmo; Vene, Varmo (July 2005). Horváth, Zoltán (ed.). The Essence of Dataflow Programming (PDF). First Summer School, Central European Functional Programming. Lecture Notes in Computer Science. 4164. Budapest, Hungary: Springer-Verlag. pp. 135–167. CiteSeerX 10.1.1.62.2047. ISBN 978-3-540-46845-5.
  32. ^ Uustalu, Tarmo; Vene, Varmo (June 2008). "Comonadic Notions of Computation". Electronic Notes in Theoretical Computer Science. Elsevier. 203 (5): 263–284. doi:10.1016/j.entcs.2008.05.029. ISSN 1571-0661.
  33. ^ Power, John; Watanabe, Hiroshi (May 2002). "Combining a monad and a comonad" (PDF). Theoretical Computer Science. Elsevier. 280 (1–2): 137–162. CiteSeerX 10.1.1.35.4130. doi:10.1016/s0304-3975(01)00024-x. ISSN 0304-3975.
  34. ^ Gaboardi, Marco; Katsumata, Shin-ya; Orchard, Dominic; Breuvart, Flavien; Uustalu, Tarmo (September 2016). Combining Effects and Coeffects via Grading (PDF). 21st ACM International Conference on Functional Programming. Nara, Japan: Association for Computing Machinery. pp. 476–489. doi:10.1145/2951913.2951939. ISBN 978-1-4503-4219-3.

External links

HaskellWiki references:

  • "All About Monads" (originally by Jeff Newbern) — A comprehensive discussion of all the common monads and how they work in Haskell; includes the "mechanized assembly line" analogy.
  • "Typeclassopedia" (originally by Brent Yorgey) — A detailed exposition of how the leading typeclasses in Haskell, including monads, interrelate.

Tutorials:

Interesting cases: