?

Log in

No account? Create an account

Previous Entry | Next Entry

Про Haskell

 Создатели Haskell понимали, что, даже с учетом всех плюсов функционального программирования, без хорошей поддержки побочных эффектов их язык вряд ли станет популярным, и в качестве решения выбрали монады.
Рассмотрим вычислитель с целыми константами и оператором целочисленного деления

  data Term = Con Int | Div Term Term

  eval :: Term → Int
  eval(Con a) = a
  eval(Div u v) = eval u / eval v

Вопрос: как его модифицировать, чтобы при делении на нуль генерировалось исключение?

Исключение - это побочный эффект, а Haskell - функциональный язык, поэтому ничего похожего на throw new DivException(...) просто так написать не получится.

Проявим изобретательность и перейдем от целых чисел к выражениям, принимающим одну из двух форм, числа или исключения, в зависимости от того, было деление на ноль или нет.

  data M a = Raise Exception | Just a
  type Exception = String

  eval :: Term → M Int
  eval(Con a) = Just a
  eval(Div u v) = case eval u of
    Raise e → Raise e
    Just x →
      case eval v of
        Raise e → Raise e
        Just y →
          if b == 0 then Raise "divide by zero" else Just (x / y)

Все отлично, задача решена, но при такой реализации неудобно добавлять новые операторы - приходится писать одинаковые конструкции:

  eval(Mul u v) = case eval u of
    Raise e → Raise e
    Just x →
      case eval v of
        Raise e → Raise e
        Just y → Just (x * y)

Тут на помощь приходят монады :)

Определим два оператора, один - return, другой - bind

  return :: a → M a
  (>>=) :: M a → ( a → M b ) → M b

  return x  = Just x
  (>>=) m g = case m of
    Raise e → Raise e
    Just x → g x

и перепишем вычислитель

eval(Div u v) = eval u >>= ( \ x → eval v >>= ( \ y → if y==0 then Raise "divide by zero" else Just (x / y) ) )
eval(Mul u v) = eval u >>= ( \ x → eval v >>= ( \ y → Just (x * y) ) )

Запись сократили, но то, что монады - это хорошее решение, пока что не очевидно. Также подумали разработчики Haskell и спрятали все лямбды и бинды за do-нотацией - синтаксическим сахаром, позволяющим писать код в императивном стиле:

eval(Div u v) = do {
  x ← eval u;
  y ← eval v;
  if y==0 then Raise "divide by zero" else Just (x / y);
}
eval(Mul u v) = do {
  x ← eval u;
  y ← eval v;
  return (x * y)
}

Для того, чтобы и на семантическом уровне не возникало проблем, все монады Haskell должны удовлетворять трем законам:
return не выполняет ни каких вычислений:
  1. m >>= return = m  //правая единица
  2. return x >>= f = f x  //левая единица
результат зависит от последовательности операторов, но не от их группировки
  3. ( m >>= f ) >>= g = m >>= ( \ x → f x >>= g)  //ассоциативность

Литература:
  1. Monads for functional programming. Philip Wadler. 1992
  2. http://en.wikibooks.org/wiki/Haskell/Understanding_monads

Comments

( 6 comments — Leave a comment )
andrey_malets
Jan. 28th, 2010 09:09 pm (UTC)
Виталик, а почему ты до сих пор не посещаешь лукачёвский семинар по функциональному программированию? Там между прочим про всякие более адвансед вещи разговаривают и целый семестр уж ;)
vitaly_kosenko
Jan. 29th, 2010 04:41 am (UTC)
Потому, что во всем это разобраться мне понадобилось лишь в конце семестра:) Да и так у меня сразу тыщи для английского образовались
andrey_malets
Jan. 29th, 2010 06:22 am (UTC)
А сейчас интереса нет продолжать заниматься?
vitaly_kosenko
Jan. 29th, 2010 06:25 am (UTC)
Есть интерес. А какие у тебя предложения?
andrey_malets
Jan. 29th, 2010 06:28 am (UTC)
Хм, предложение было неявно сформулировано в вопросе первого комментария :)
vitaly_kosenko
Jan. 29th, 2010 06:33 am (UTC)
Так и понял
( 6 comments — Leave a comment )