Здравствуйте, gandjustas, Вы писали:

G>На F# и проще, и понятнее, и делал уже, но я хотел еще простые монады (Identity, Maybe, State) с помощью Linq сделать.

CPS и Maybe монады на LINQ functional-dotnet

Здравствуйте, gandjustas, Вы писали:

G>Здравствуйте, Пельмешко, Вы писали:

П>>Здравствуйте, Jack128, Вы писали:

J>>>А ты не мог бы преобразовать labelMonad в код без этой нотации??

П>>Легко
П>>

П>>let rec labelMonad = function
П>>  | Leaf(x) ->
П>>    state.Bind(getState, fun s ->
П>>     state.Bind(setState(s+1), fun () ->
П>>      state.Return(Leaf(x,s))))
П>>  | Branch(a,b) ->
П>>    state.Bind(labelMonad a, fun l ->
П>>     state.Bind(labelMonad b, fun r ->
П>>      state.Return(Branch(l,r))))
П>>

Хм. Я правельно понимаю, что функция без параметров и функция, которая принимает unit в F# — совместимы??

Здравствуйте, Jack128, Вы писали:

J>Хм. Я правельно понимаю, что функция без параметров и функция, которая принимает unit в F# — совместимы??

Функция вида

let f () = 1

имеет тип unit -> int

А вот значение uint получит нельзя

Здравствуйте, Jack128, Вы писали:

J>Хм. Я правильно понимаю, что функция без параметров и функция, которая принимает unit в F# — совместимы??

По сути unit — это и есть параметр.
bind — обобщённая функция, вторым аргументом получает ('a -> M<'b>), а под такой тип подходит и функция (unit -> ...), то есть 'a может быть и unit'ом.

Здравствуйте, gandjustas, Вы писали:

G>А вот значение uint получит нельзя

Мона, по сути () в параметрах — это всегда истинный паттерн матчинг по значению (которое у юнита всегда одно). С помощью as можно получить значение, с которым сматчился шаблон ():

let f (() as x) = x

Здравствуйте, gandjustas, Вы писали:

G>Здравствуйте, Jack128, Вы писали:


G>

G>

J>>Хм. Я правельно понимаю, что функция без параметров и функция, которая принимает unit в F# — совместимы??

G>Функция вида
G>

G>let f () = 1
G>

G>имеет тип unit -> int

G>А вот значение uint получит нельзя

В смысле unit ?? Почему нельзя, вроде компилится:

let unitValue = printf "%A" 10

правда на самом деле unitValue — это null, при попытке вызова unitValue.GetTYpe() — NRE вылетает.

Здравствуйте, Jack128, Вы писали:

J>правда на самом деле unitValue — это null, при попытке вызова unitValue.GetTYpe() — NRE вылетает.
Ну я именно это и имел ввиду

Здравствуйте, Jack128, Вы писали:

Вот пробую написать простейшую, как понимаю, монаду MayBe

type MayBe<'a> = 
  | Just of 'a
  | None

type MayBeBuilder() = 
     (*  'a -> M<'a>  *)
     member b.Return(a) =
        Just a

     (*  M<'a> * ('a -> M<'b>) -> M<'b>  *)
     member b.Bind(m, g) =
        match m with
            | Just a -> g a
            | None   -> None

let mayBe = MayBeBuilder()

let getNone() = None

let result = mayBe {
    let! tmp = Just 10
    let! noneValue = None
    return tmp + noneValue    
 }
 
printf "%A" result

вроде всё работает. Но с практической точки зрения напрягает, что я должен каждое значение связывать оператором let!

то есть хотелось бы вместо:

let getNone() = None
let getTen() = Just 10

let result = mayBe {
   let! ten = getTen()
   let! none = getNone()
   return ten + none
}

писать:

let result = mayBe {
    return getTen() + getNone()
 }

такое возможно

<skipped/>

можно сделать lift, заточенный под maybe (не уверен, что на F# можно написать обобщенный lift)

let liftToMaybe f x y = maybe {
    let! vx = x
    let! vy = y
    return f vx vy
    }
    
let res = 
    maybe {
        let (++) = liftToMaybe (+)
        return! get10() ++ get1()
    }

Здравствуйте, gandjustas, Вы писали:

G>Конекретно меня интересует как протягивается этот самый state черезер каскад из лямбда-функций

Если не думать о монадах, то получится примерно следующее.

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

Например, при проходе по структуре для получения некоего результата на императивном языке мы можем написать что-то вроде:

def sum(list: List of int)
    summa = 0

    for (item in list)
        summa += item

    return summa

Более сложные алгоритмы делают работу с состоянием ещё более запутанным

def foo
    x = 0
    y = bar(x)
    x = zzz(x, y)
    ...

Итак, что характеризует состояние? Важность порядка исполнения и изменяемые переменные. На ФЯ эти свойства эмулируют с помощью так называемых аккумуляторов. Это приём, когда в функцию, помимо необходимых ей аргументов, также передают некую переменную, эмулирующую изменяюмую переменную:

def sum(list: List of int, accum: int)
    if list.empty
        then return accum
        else return sum(tail(list), accum + head(list))

Для сложного алгоритма это выглядит как то так

let (x1,s1) = f0(x0, s0)
    (x2,s2) = f1(x1, s1)
    (x3,s3) = f2(x2, s2)
 in x3

Переменная s1 здесь зависит от того, известна ли s0, а переменная s2 — от того, известна ли s1. Полученная цепочка s0->s1->s2 эмулирует у нас некоторое состояние, относящееся к этому вычислению. xN характеризуют у нас аргументы функций fN, на самом деле они вовсе не должны быть цепочкой, но иногда они зависят друг от друга и, разумеется, состояния.

Допустим теперь, что мы хотим скрыть явное использование переменных sN, потому что алгоритм гораздо симпатичнее запишется в виде

global s

x1 = f0(x0)
x2 = f1(x1)
x3 = f2(x2)

return x3

где функции fN меняют глобальное состояние s. В чистом функциональном языке это можно сделать объединив вычисления с помощью некоего комбинатора. Т.е. сначала мы вычисляем f0(x0), а затем вычисляем f1(x1). Но так как определение x1 у нас отсутствует, то нам придётся завернуть вычисление f1(x1) в лямбду с аргументом x1

f0(x0) THEN (x1 => f1(x1)) THEN (x2 => f2(x2)) THEN (x3 => RETURN x3)

THEN — инфиксный комбинатор двух аргументов. Какой тип он имеет? Вспомним, чем на самом деле являются функции fN (смотрим на код (x1,s1) = f0(x0, s0))

fN :: a -> s -> (r,s)

Т.е. это функция, принимающая некий важный для неё аргумент (или несколько аргументов) и состояние и возвращающая тапл с результатом и состоянием. Я извиняюсь, что написал тип в таком стиле, но привычный алголоподобный стиль будет более коряв.

Рассмотрим выражение f0(x0) THEN (x1 => f1(x1)).

Слева у нас f0(x0). f0 :: a -> s -> (r,s), но так как аргумент мы уже применили, то (a ->) убираем из типа. Получается, что f0(x0) имеет тип s -> (r,s), т.е. это выражение ожидает переменную состояния (тип s), и возвращает тапл с результатом и новым состоянием. Это тип первого аргумента THEN.

Справа у нас x1 => f1(x1). Тип этой лямбды r -> s -> (new_r, s). Здесь стоит тип new_r, т.к. тип результата вычисления может отличаться от типа аргумента. Что должен возвращать x THEN y? Что-то, что можно снова применить к THEN, т.е. что-то с типом (s -> (new_r, s)).

Итак! Полный тип THEN будет выглядеть так

THEN :: (s -> (r,s)) -> (r -> s -> (new_r, s)) -> (s -> (new_r, s))

Тип очень сложный, но в нём можно заметить повторяющийся кусок, который мы выделим в синоним типа (алиас).

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

THEN :: State<s,r> -> (r -> State<s, new_r>) -> State<s, new_r>

Получилось попроще. Мало того, теперь мы видим, что из себя представляет вычисление с состоянием. Это просто функция (!), которая получает состояние и возвращает результат с новым состоянием. Семантически монада состояния очень проста. Функция. Принимает на вход состояние. Возвращает результат и новое состояние.

Итак! Тип для THEN мы получили, теперь попробуем его реализовать. Это как раз несложно. Как видно из его типа (исходного, без использования алиаса) на самом деле THEN имеет 3 аргумента, а не 2. Третий аргумент имеет тип s и это начальное состояние, передаваемое в цепочку вызовов f0->f1.

def THEN(calc1: s => (r,s), calc2: r,s => (new_r,s), state0: s): (new_r, s)
    // у нас две функции и одна нормальная переменная
    // Пока применить эту переменную мы можем только к одной функции
    (res, state1) = calc1(state0)
    // у нас есть аргументы для второй функции
    (new_res, state2) = calc2(res, state1)
    // этот результат мы и возвращаем
    return (new_res, state2)

По сути, это наше let-выражение с явным аккумулятором. С RESULT всё ещё проще. Он принимает некий аргумент, а должен вернуть State<s,a>

def RESULT(val: a, state: s): (a,s)
    // ну что мы ещё можем вернуть?
    return (val, state)

Вот и всё! Теперь мы можем писать так

f0(x0)  THEN (x1 =>
f1(x1)) THEN (x2 =>
f2(x2)) THEN (x3 =>
RETURN x3)

Для более удобной работы с состоянием напишем ещё пару функций.

Получение состояния. Вспомним, что состояние в наших вычислениях на комбинаторе THEN неявное. Чтобы сделать его явным мы должны передать его в результат:

def GET(state: s): (s,s)
    return (state, state)

Изменение состояния. Тут всё просто. Аргумент у нас — новое состояние, его мы и должны вернуть в результирующем состоянии

def PUT(newState: s, state: s): ((),s)
    // забываем про state, у нас есть новое состояние
    return ((), newState)

Тут мы видим, что PUT возвращает () — семантически это отсутствие результата или неважный результат, именно так мы и будем его интерпретировать. Но, т.к. у нас есть такой тип результата, то неплохо было бы иметь близнеца THEN, который не использует результат. Назовём его THEN_

// отличие! calc2 не принимает аргумент типа r
def THEN_(calc1: s => (r,s), calc2: s => (new_r,s), state0: s): (new_r, s)
    // объединяем вычисления, не использую результат первого во втором
    calc = calc1 THEN (_ => calc2)
    // запускаем вычисление с состоянием
    return calc(state0)

Теперь мы можем писать так

def TICK: State<int, ()>
    GET THEN (state =>
    PUT (state + 1))

def TICK3: State<int, ()>
    TICK THEN_
    TICK THEN_
    TICK

Вот и всё. Никаких монад.

Здравствуйте, lomeo, Вы писали:

Супер!!!

L>Вот и всё. Никаких монад.
Ага, почти

Здравствуйте, desco, Вы писали:

Не, ну так понятно. А вот в таком случае например что делать?

type Record1 = { age: int MayBe }
type Record2 = { rec1: Record1 MayBe }


let getRec2() = Just { rec1 = Just { age = Just 10 } }

let age = mayBe {
    let! rec2 = getRec2()
    let! rec1 = rec2.rec1
    let! age = rec1.age
    return age
}

Здравствуйте, Jack128, Вы писали:

J>Здравствуйте, desco, Вы писали:

J>Не, ну так понятно. А вот в таком случае например что делать?

J>

J>type Record1 = { age: int MayBe }
J>type Record2 = { rec1: Record1 MayBe }


J>let getRec2() = Just { rec1 = Just { age = Just 10 } }

J>let age = mayBe {
J>    let! rec2 = getRec2()
J>    let! rec1 = rec2.rec1
J>    let! age = rec1.age
J>    return age
J>}
J>

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

Здравствуйте, desco, Вы писали:

D>можно сделать lift, заточенный под maybe (не уверен, что на F# можно написать обобщенный lift)

поправка, если использовать member constraints, то извернутся можно

type List() = 
    static member Instance = List()
    member x.Return(v) = [v]
    member x.Bind(m, f) = List.collect f m    
let list = List()

type Maybe() = 
    static member Instance = Maybe()
    member x.Return(v) = Some(v)
    member x.Bind(m, f) = match m with | Some(v) -> f v | None -> None
let maybe = Maybe()
    
let inline ret b v = 
    (^b :  (member Return : ^v -> ^mv) (b, v))
    
let inline bind b m f = 
    (^b :  (member Bind : ^v * ^f -> ^mv) (b, m, f)) 

let inline lift2 b f x y =
    bind b x (fun x1 -> 
        bind b y (fun y1 -> ret b (f x1 y1))
    )

// None
let r = maybe {
        let (++) = lift2 maybe (+)
        return! Some(5) ++ None
    }    

// [0;2;1;3]    
let r2 = list {
        let (++) = lift2 list (+)
        return! [0;1] ++ [0;2]
    }

Здравствуйте, desco, Вы писали:

D>Здравствуйте, desco, Вы писали:

D>>можно сделать lift, заточенный под maybe (не уверен, что на F# можно написать обобщенный lift)

D>поправка, если использовать member constraints, то извернутся можно
D>

D>type List() = 
D>    static member Instance = List()
D>    member x.Return(v) = [v]
D>    member x.Bind(m, f) = List.collect f m    
D>let list = List()

D>type Maybe() = 
D>    static member Instance = Maybe()
D>    member x.Return(v) = Some(v)
D>    member x.Bind(m, f) = match m with | Some(v) -> f v | None -> None
D>let maybe = Maybe()
    
D>let inline ret b v = 
D>    (^b :  (member Return : ^v -> ^mv) (b, v)) // А что это такое и где об этом мона почитать???
    
D>let inline bind b m f = 
D>    (^b :  (member Bind : ^v * ^f -> ^mv) (b, m, f)) 

D>let inline lift2 b f x y =
D>    bind b x (fun x1 -> 
D>        bind b y (fun y1 -> ret b (f x1 y1))
D>    )

D>// None
D>let r = maybe {
D>        let (++) = lift2 maybe (+)
D>        return! Some(5) ++ None
D>    }    

D>// [0;2;1;3]    
D>let r2 = list {
D>        let (++) = lift2 list (+)
D>        return! [0;1] ++ [0;2]
D>    }    
D>

По-моему пример с монадой (workflow) Maybe через чур хаскельный. В F# все таки энергичный порядок вычислений. Это нужно учитывать. Например, в книге Expert F# вводится явная ленивость через лямбду. То есть вместо 'a option внутри монады используется функция unit -> 'a option.

Здравствуйте, lomeo, Вы писали:

Елы-палы. Получается без пяти минут статься.

Добавил бы введение и оформил бы в нашем шаблоне. А то ведь через пару недель это сообщение канет в лету и про него все забудут. А так всегда будет на виду и найти можно будет легко.

 

Чё?

 

Здравствуйте, VladD2, Вы писали:

Q>>Дваждую статью
VD>Чё?

Забей. Просто хотел поддержать твоё предложение, адресованное lomeo, о написании статьи про монаду State.