모나드 첫걸음

람다 함수

(function (x, y) {
  return x + y;
})(1, 2);

• es6 arrow function

((x, y) => x + y)(1, 2)

(x => x + 1)(1)

모나드

컨텍스트가 있는 연속된 계산을 읽기 쉽게 만들기 위한 순수 함수형 패턴

• 컨텍스트

• 연속된 계산

• 읽기 쉽게

• 순수 함수형

• null 체크라는 컨텍스트가 있는 연속된 계산의 단순한 예

var value1 = getValue("key1");
if (value1 !== null) {
  var value2 = getValue("key2");
  if (value2 !== null) {
    ...
  }
}
else {
  return null;
}

• 계산 속에 컨텍스트가 섞여 있다면 계산의 본질을 파악하기(읽기) 어렵다.
• 컨텍스트와 계산을 분리하면 컨텍스트를 재사용할 수 있다.
• 순수 함수형으로 절차적으로 보이는 연속된 계산을 쉽게 표현하기 어렵다.
• 쉬운 순서대로 알아보자
  • 읽기 쉽게
  • 순수 함수형
  • 연속된 계산
  • 컨텍스트

컨텍스트가 있는 연속된 계산을 읽기 쉽게 만들기 위한 순수한 함수형 패턴

• 코드는 추상화(abstraction)를 통해 읽기 쉽게 만들 수 있다.
• 여러운 것과 모르는 것(C 계열 문법, 언어가 아닌 것), 학습 비용
• 모든 코드를 하나의 함수에 쓰지 않는 이유는 복잡하기 때문

(str "Hello" "World" "!")
;; str????

• 축약의 단순함과 풀어쓰는 것과 장황함
  • multiplication vs *
    • 1 multiplication 2 vs 1 * 2
  • uniqueness vs ∃!
    • ∃! n ∈ ℕ: n + 5 = 2n. vs uniqueness n exists ....

(defn str
  "With no args, returns the empty string. With one arg x, returns
  x.toString().  (str nil) returns the empty string. With more than
  one arg, returns the concatenation of the str values of the args."
  {:tag String
   :added "1.0"
   :static true}
  (^String [] "")
  (^String [^Object x]
   (if (nil? x) "" (. x (toString))))
  (^String [x & ys]
     ((fn [^StringBuilder sb more]
          (if more
            (recur (. sb  (append (str (first more)))) (next more))
            (str sb)))
      (new StringBuilder (str x)) ys)))

컨텍스트가 있는 연속된 계산을 읽기 쉽게 만들기 위한 순수한 함수형 패턴

• 순수

  • 부수 효과가 없다.

    function inc(x) {
      console.log("x:", x); // 부수 효과!
      return x + 1;
    }

  • 상태가 없다.

    var state = 1;
    state = 2; // 상태를 변경!

  • 글로벌 값도 없다.

    var y = 1;
    
    function calc(x) {
      return x + y; // 글로벌 y를 참조!
    }

  • 절차도 없다.

    // 아레 절차 대로 실행!
    var x = 1;
    var y = 2;
    x + y;

• 대부분의 언어는 순수하지 않은 기능을 제공한다.

• 순수한 프로그래밍의 장점은 많지만 여기서 이야기하지 않는다.

• 모나드는 순수함을 전제로 한다. 따라서 순수한 것과 섞어 사용한다면 의미가 없다.

컨텍스트가 있는 연속된 계산을 읽기 쉽게 만들기 위한 순수한 함수형 패턴

절차적

var x = 1;
var y = 2;
var result = x + y;

순수 함수형 절차적 표현

((x =>
  (y =>
    x + y))(1))(2)

• 절차적인 스타일에 비해 읽기 어렵다.

들여쓰기를 이용해서 보기 좋게 만들기

((x =>
    (y =>
           x + y))
 (1))
    (2)

helper 함수를 이용해서 더 보기 좋게 만들기

• 인자 하나와 함수를 받아 함수에 인자를 적용하는 함수

function bind (mv, f) {
  return f(mv);
};

• bind 함수를 사용해 보기

bind(1, x =>
          bind(2, y =>
                    x + y));

• 들여쓰기를 보기 좋게 해보자

bind(1, x =>
bind(2, y =>
     x + y));

• 절차적 스타일과 비교해보기

var x = 1;
var y = 2;
var result = x + y;

• bind 함수도 있고 괄호도 있고 해서 복잡해 보인다?
• var도 있고 =도 있고 ;은 왜 복잡해 보이지 않는가?
• var, =, ;는 이미 마음 속에 추상화 하지만 bind 함수는 내 마음속에 아직 익숙하지 않기 때문이다.
• 이제 bind 함수나 괄호 같은 것은 봐도 못본 척하자. 필요한 것은 x에 1을 y에 2를 바인딩하고 x와 y를 더하는 것

1 x
2 y
  x + y

• 억지스럽다고 생각하겠지만 순수 함수로 연속된 계산을 읽기 쉽게 표현했다.

모나드 패턴

• 연속된 계산을 표현하는 추상 패턴

bind(계산, 계산 결과를 바인딩할 기호 => // 줄
bind(계산, 계산 결과를 바인딩할 기호 => // 줄
     결과));                      // 줄

• bind 함수를 다시 보자

function bind (mv, f) {
  return f(mv);
};

• 모나드 패턴은 유지하고 bind 함수의 구현 방식에 따라 모나드 특성이 결정된다.
• 위 예제는 단순히 절차적 컨텍스트만 가지는 모나드이고 identity 모나드라고 부른다.

컨텍스트가 있는 연속된 계산을 읽기 쉽게 만들기 위한 순수한 함수형 패턴

• 계산 과정을 감싸고 있는 공통된 이야기
• 컨텍스트의 예
  • 계산 과정에서 결과가 nil인 경우 (maybe 모나드)
  • 계산 과정에 로그를 기록해야하는 경우 (writer 모나드)
  • 계산 과정 중에 config가 필요한 경우 참조해야 하는 경우 (reader 모나드)
  • 계산 과정 중 상태가 필요한 경우 (state 모나드)

계산 과정에서 결과가 nil인 경우 다음 계산을 하지 않는 컨텍스트 예제

• 계산 과정 null이 나올 수 있는 예제

function getName (id) {
  if (id == 1) {
    return "WORLD";
  }
  else {
    return null;
  }
}

bind( getName(2)      , x =>
bind( x.toLowerCase() , y =>
      "Hello, " + y + "!"
));

Uncaught TypeError: Cannot read property 'toLowerCase' of null
    at monad.html:77
    at bind (monad.html:64)
    at monad.html:76
    at monad.html:81

• bind 함수 수정

function bind (mv, f) {
  if (mv != null) {
    return f(mv);
  }
  return null;
};

bind( getName(2)      , x =>
bind( x.toLowerCase() , y =>
      "Hello, " + y + "!"
));
// => null

• 계산 중 null이 나오면 다음 계산을 진행하지 않고 최종 결과를 null로 처리하는 컨텍스트를 가지는 모나드를 maybe 모나드라고 한다.

• 하스켈에서 maybe 모나드

Just 3 >>= (\x ->
Just 4 >>= (\y ->
Just (x + y)))  

계산 과정에 로그와 같이 뭔가 계속 쓸 수 있어야 하는 경우 (writer 모나드)

var result =
bind( 1,                   x =>
bind( logging("x: " + x),  _ =>
bind( 2,                   y =>
      x + y
)));

// result는 로그와 결과가 함께 들어 있어야 한다.

getLog(result);
// => ["x: 1"]
// 로그는 계속 쌓여야 하니 배열에 넣자!

getValue(result);
// => 3

• 로그와 계산 결과를 담을 데이터 (타입?)

// 객체에 담을 수도 있지만 예제를 간단하게 하기 위해서
var result = [3, ["x: 1"]];

// v는 [x, y] 형태로 여야한다는 암묵적 타입
function getLog(v) {
  return v[1];
}

function getValue(v) {
  return v[0];
}

• bind 함수는 어떻게 생겨야 하나?

// oldResult는 [x, []] 여야 한다는 암묵적 타입
function bind(oldResult, f) {
  var oldValue = oldResult[0];
  var oldLogs = oldResult[1];
  var newResult = f(oldValue);
  var newValue = newResult[0];
  var newLogs = newResult[1];
  return [newValue, oldLogs.concat(newLogs)];
}

var result =
bind( 1,                   x =>
bind( logging("x: " + x),  _ =>
bind( 2,                   y =>
      x + y
)));

• 체크는 안해 주지만 타입 에러가 발생

function bind(oldResult, f) { ... }

bind(1, function(x) { ..

// 1 != oldResult 기대하는 타입이 아니다!

• 일반 값을 bind 함수가 받을 수 있는 타입으로 만들어 주자!

function bind(oldResult, f) { ... }

bind([1, []], function(x) { ..

• 일반 값을 bind 함수가 받을 수 있는 타입으로 만들어주는 helper 함수를 만들자!

function mreturn(v) {
  return [v, []];
}

• 일반적으로 사용하기 위해서 함수 이름을 newLogType 대신 mreturn을 사용했다. 모나드에서 보통 return이라고 부르지만 자바스크립트에서 return이 예약어라서 mreturn으로 했다.

function bind(oldResult, f) { ... }

bind(mreturn(1), function(x) { ..

var result =
bind( mreturn(1),          x =>
bind( logging("x: " + x),  _ =>
bind( mreturn(2),          y =>
      mreturn(x + y) // 최종 결과도 타입을 맞춰 준다.
)));

• logging 함수는 어떻게 만들어야 하나?

function logging(log) {
  return [null, [log]];
}

• 값이 있어야하는 부분이 null인 이유는 다음 계산 과정에서 사용하지 않기(_) 때문이다.
• 완성 버전

function bind(mv, f) {
  var vv = f(mv[0]);
  return [vv[0], mv[1].concat(vv[1])];
}

function mreturn(v) {
  return [v, []];
}

function logging(log) {
  return [null, [log]];
}

function getLog(v) {
  return v[1];
}

function getValue(v) {
  return v[0];
}

var result =
bind( mreturn(1),          x =>
bind( logging("x: " + x),  _ =>
bind( mreturn(2),          y =>
      mreturn(x + y)
)));

getLog(result);
// ["x: 1"]
getValue(result);
// 3

• 계산 과정중 계산 결과에 영향을 주지 않고 다른 곳에 값을 기록할 수 있는 컨텍스트를 가지는 모나드를 writer 모나드라고 한다.
• mreturn helper 함수는 일반 값을 모나드 컨텍스트 안에서 사용할 수 있는 형태(타입)으로 바꿔주는 함수다.
• 모나드는 bind 함수와 return 함수에 따라 특성이 결정된다.
• writer 모나드에서 logging 함수는 tell 함수라고 부른다.

모노이드

• 합치는 것에 대한 추상화(인터페이스)
• concat 대신 추상적인 함치는 방법에 대한 append 함수 정의

  function bind(mv, f) {
    var vv = f(mv[0]);
    return [vv[0], mv[1].concat(vv[1])]; // -> mv가 모노이드면 append를 사용
  }

• 빈 배열 대신 합쳐도 자신이 나오는 empty 타입 정의

  function mreturn(v) {
    return [v, []]; // -> [] 대신 mv 타입에 대한 empty 함수를 사용, 타입 추론이 약한 언어에서는 재사용하려면 조금 문법이 복잡하다.
  }

계산 과정 중에 config와 같이 언제든 참조할 수 있는 환경 값이 필요한 경우 (reader 모나드)

var config = { debug: true };

function calc1 (x) {
  return 1 + x;
}

function calc2 (y) {
  if (config.debug == true) { // 컨텍스트 외부 값을 값을 참조
    return 2 + y;
  }
  else {
    return 0;
  }
}

var x = calc1(1);
var y = calc2(x);
var result = x + y;

• calc2는 전역 변수인 config를 참조한다.

• 전역 변수를 사용하지 않는 calc2

function calc1 (x) {
  return 1 + x;
}

function calc2 (y, config) {
  if (config.debug == true) {
    return 2 + y;
  }
  else {
    return 0;
  }
}

var config = { debug: true };
var x = calc1(1);
var y = calc2(x, config);
var result = x + y;

• 모나드로 풀어보자.

var result =
bind( mreturn(calc1(1))         , x =>
bind( ask()                     , config =>
bind( mreturn(calc2(2, config)) , y =>
      mreturn(x + y)
)));

result({debug: true});

• bind 함수와 mresult 함수

function bind(mv, f) {
  return r => f(mv(r))(r);
}

function mreturn(v) {
  return r => v;
}

• 구조가 어렵지만 writer 타입과 다르게 환경 값을 저장하기 위해 함수 값을 사용한다는 것을 알 수 있다.

• 환경 값을 읽어오기 위한 도우미 함수

function ask() {
  return r => r;
}

function calc1 (x, config) {
  return 1 + x;
}

function calc2 (y, config) {
  if (config.debug == true) {
    return 2 + y;
  }
  else {
    return 0;
  }
}

var result =
bind( mreturn(calc1(1))         , x =>
bind( ask()                     , config =>
bind( mreturn(calc2(2, config)) , y =>
      mreturn(x + y)
)));

result({debug: true});
// 6
result({debug: false});
// 2

• 처음에 환경 값을 넘기고 계산 과정 중 언제든 참조할 수 있도록 하는 컨텍스트를 가지는 모나드를 reader 모나드라고 한다.

계산 과정 중 읽고 쓸 수 있는 상태가 필요한 경우 (state 모나드)

• 순수 함수에는 상태가 없지만 모나드로 상태를 표현할 수 있다.

var state = undefined;
var x = 1;
state = 1; // put state
y = state; // get state
var result = x + y;

• 모나드로 상태를 표현해 보기

var result =
bind( mreturn(1)     , x =>
bind( put(x)         , _ =>
bind( get()          , y =>
      mreturn(x + y)
)));

getValue(result);

• bind와 mreturn 함수

function bind(mv, f) {
  return s => {
      [v, ss] = mv(s);
      return (f(v))(ss);
  }
};

function mreturn(v) {
  return s => [v, s];
};

• reader 모나드처럼 모나드 값이 함수로 되어 있다.
• 상태 값을 쓰거나 읽을 수 있는 helper 함수

function put(s) {
  return _ => [null, s];
};

function get() {
  return s => [s, s];
};

function getValue(s) {
  return s()[0];
};

function getState(s) {
  return s()[1];
};

var result =
bind( mreturn(1)     , x =>
bind( put(x)         , _ =>
bind( get()          , y =>
      mreturn(x + y)
)));

getValue(result);
// 2

• 계산 과정 중 언제든 하나의 상태를 쓰거나 읽을 수 있는 컨텍스트를 가지는 것을 state 모나드라고 부른다.

정리

컨텍스트가 있는 연속된 계산을 읽기 쉽게 만들기 위한 순수한 함수형 패턴

bind(mreturn(1), x => bind( mreturn(2), y => mreturn(x + y)));

모나드 값 -> bind -> 값 -> f1 -> 값 -> return -> 모나드 값 -> bind -> 값 -> f2 -> 값 -> return -> 모나드 값 -> ....

값 -> f -> 값 ==변환==> 값 -> f2 -> 값

모나드와 타입과 다형성

데이터와 함수를 묶기

• writer 모나드에서 bind 함수와 result 함수

function bind(v, f) {
  var vv = f(v[0]);
  return [vv[0], v[1].concat(vv[1])];
}

function mreturn(v) {
  return [v, []];
}

• bind에 전달되는 v 데이터는 [x, []] 타입이다.

• mreturn에서 나오는 데이터는 [x, []] 타입이다.

• [x, []] 타입 대신 Writer 타입을 만든다면 ...

function Writer(value, extra) {
  this.value = value;
  this.extra = extra;
  this.bind = function(f) {
    var w = f(this.value);
    return new Writer(w.value, this.extra.concat(w.extra));
  };
}

Writer.return = function(v) {
  return new Writer(v, []);
};

Writer.logging = function(log) {
  return new Writer(null, [log]);
};

var result =
Writer.return(1)         .bind(x =>
Writer.logging("x: " + x).bind(_ =>
Writer.return(2)         .bind(y =>
Writer.return(x + y);
)));

// result.extra;

데이터와 함수를 분리

var writer = {
  bind : (mv, f) => {
    var vv = f(mv[0]);
    return [vv[0], mv[1].concat(vv[1])];
  },
  return : v => [v, []];
};

var domonad = (monad, f) => f(monad.bind, monad.return);

domonad(writer, (bind, mreturn) =>
  bind( mreturn(1),         x =>
  bind( logging("x: " + x), _ =>
  bind( mreturn(2),         y =>
  mreturn(x + y)
))));

• bind, mreturn 인터페이스
• do 노테이션

thing1 >>= (\x -> func1 x >>= (\y -> thing2 
       >>= (\_ -> func2 y >>= (\z -> return z))))
       
do 
  x <- thing1
  y <- func1 x
  thing2
  z <- func2 y
  return z

• 데이터와 함수를 묶거나 데이터와 함수를 분리하거나 다형성은 가능하다. expression problem(https://en.wikipedia.org/wiki/Expression_problem)
• 하스켈 타입 추론에 의한 다형성

  type GameValue = Int
  type GameState = (Bool, Int)
  
  playGame :: String -> State GameState GameValue
  playGame []     = do
      (_, score) <- get
      return score
  
  playGame (x:xs) = do
      (on, score) <- get
      case x of
           'a' | on -> put (on, score + 1)
           'b' | on -> put (on, score - 1)
           'c'      -> put (not on, score)
           _        -> put (on, score)
      playGame xs
  
  startState = (False, 0)
  
  main = print $ evalState (playGame "abcaaacbbcabbab") startState

다루지 않은 내용

• 펑터와 어플리커티브 펑터

instance Functor m where
    fmap = liftM
 
instance Applicative m where
    pure  = {- move the definition of `return` from the `Monad` instance here -}
    (<*>) = ap

• 모나드의 추가 인터페이스

class Monad m where
  (>>=)  :: m a -> (  a -> m b) -> m b
  (>>)   :: m a ->  m b         -> m b
  return ::   a                 -> m a
  fail   :: String -> m a

• 모나드의 법칙

return a >>= k                  =  k a
m        >>= return             =  m
m        >>= (\x -> k x >>= h)  =  (m >>= k) >>= h

• 모나드 합성
  • Monad Transformer (https://page.mi.fu-berlin.de/scravy/realworldhaskell/materialien/monad-transformers-step-by-step.pdf)
  • Effect (http://okmij.org/ftp/Haskell/extensible/tutorial.html)

가치

• 순수 함수안에서 가치를 가진다
  • 언어에서 순수하지 않은 것을 허용하지 않는다면 코드의 표현력을 높혀준다.
  • 계산 과정에 중복 함수를 제거
  • 계산 과정에서 컨텍스트를 로직과 분리해서 생각
• 함수형 프로그래밍 센스
• 비 순수 함수형 언어라면 언어의 철학에 맞게 언어에서 제공하는 비순수 기능과 함수형 기능을 적절히 활용하는 것이 좋다.

bind(1, x =>
bind(2, y =>
     x + y));

var x = 1;
var y = 2;
var result = x + y;

사례

https://wiki.haskell.org/Monad

• Identity monad - the trivial monad.
• Optional results from computations - error checking without null.
• Random values - run code in an environment with access to a stream of random numbers.
• Read only variables - guarantee read-only access to values.
• Writable state - i.e. log to a state buffer
• A supply of unique values - useful for e.g. guids or unique variable names
• ST - memory-only, locally-encapsulated mutable variables. Safely embed mutable state inside pure functions.
• Global state - a scoped, mutable state.
• Undoable state effects - roll back state changes
• Function application - chains of function application.
• Functions which may error - track location and causes of errors.
• Atomic memory transactions - software transactional memory
• Continuations - computations which can be interrupted and resumed.
• IO - unrestricted side effects on the world
• Search monad - bfs and dfs search environments.
• non-determinism - interleave computations with suspension.
• stepwise computation - encode non-deterministic choices as stepwise deterministic ones
• Backtracking computations
• Region allocation effects
• LogicT - backtracking monad transformer with fair operations and pruning
• concurrent events and threads - refactor event and callback heavy programs into straight-line code via co-routines
• QIO - The Quantum computing monad
• Pi calculus - a monad for Pi-calculus style concurrent programming
• Commutable monads for parallel programming
• Simple, Fair and Terminating Backtracking Monad
• Typed exceptions with call traces as a monad
• Breadth first list monad
• Continuation-based queues as monads
• Typed network protocol monad
• Non-Determinism Monad for Level-Wise Search
• Transactional state monad
• A constraint programming monad
• A probability distribution monad
• Sets - Set computations
• HTTP - http connections as a monadic environment
• Memoization - add memoization to code