Здравствуйте, gandjustas, Вы писали:
G>Разметка двоичного дерева на C# с использованием State Monad и Linq
G>Кто-нибудь может объяснить как оно работает?
мне кажется работает очень просто. Бегает рекурсивно по дереву, когда добегает до Leaf, инкрементит его на еденичку от текущего значения, сохраненного в глобальной пеерменной^W^W прошу прощения, монаде и создает новую ноду с разметкой.
код после небольшого рефакторинга
комментарии мои
static StateMonad<int, Node<StateM<int, T>>> GetLabelMonad<T>(Node<T> tree)
{
if (tree is Leaf<T>)
{
var leaf = tree as Leaf<T>;
var m = from s in StateMonad.Get<int>() // получили текучее значение счетчика листьев из монадыfrom _ in StateMonad.Put(s + 1) // инкрементировали егоfrom r in StateMonad.Return(0,Node.Leaf(new StateM<int, T>(s, leaf.Content))) // в листе ноды теперь нода с индексомselect r;
return m;
}
else if (tree is Branch<T>)
{
// а эта ветка просто рекурсивный спуск. ничего интересного
}
else
{
throw new Exception("Invalid object type");
}
}
могу конечно ошибаться в мелочах, но общая идея должна быть такой.
Здравствуйте, Mirrorer, Вы писали:
M>Здравствуйте, gandjustas, Вы писали:
G>>Разметка двоичного дерева на C# с использованием State Monad и Linq
G>>Кто-нибудь может объяснить как оно работает? M>мне кажется работает очень просто. Бегает рекурсивно по дереву, когда добегает до Leaf, инкрементит его на еденичку от текущего значения, сохраненного в глобальной пеерменной^W^W прошу прощения, монаде и создает новую ноду с разметкой.
M>могу конечно ошибаться в мелочах, но общая идея должна быть такой.
Это как раз просто, меня интересует код связывания. Под отладчиком я вижу что и как происходит, но осознать мозгом почему так работает получается у меня с большим трудом.
Здравствуйте, gandjustas, Вы писали:
G>Это как раз просто, меня интересует код связывания. Под отладчиком я вижу что и как происходит, но осознать мозгом почему так работает получается у меня с большим трудом.
все не просто а очень просто.
на псевдокоде
using(int counter =0)
{
foreach(var leaf in tree.Leaves)
{
leaf = new Pair<int, Leaf>(counter++, leaf)
}
}
У нас есть контекст, внешний по отношению алгоритму обработки.
мы можем из него что-то читать и что-то в него записывать.
Его вполне можно было бы заменить на такую штуку
interface IHaveContext<T>
{
T GetCurrentContext();
SetCurrentContext(T val);
}
теперь делаем static переменную, реализовывающую этот интерфейс. Это получится конечно уже не сишарп, а черт знает что, но тут главное уловить идею.
static context:IHaveContext<int>
foreach(var leaf in tree.Leaves)
{
var currentContext = context.GetCurrentConext();
context.SetCurrentContext(currentContext.Value +1);
leaf = new Pair<int, Leaf>(currentContext.Value, leaf)
}
Конкретно в этой задаче контекст достаточно прост, чтобы его можно было описать банальными геттером и сеттером. Из пушки по воробьям короче
Но для других контекстов он может быть сложнее, и может появиться логика влияния внешних контекстов на внутренние.
Тут явно видно что внешний контекс дает возможность выполнения внутренним. Типа транзакционность.
Такие развесистые ифы имеют мало кайфа в написании и поддержке. Поэтому их обычно выносят в интерфейсы
//простецкий интерфейс.
//Метод принимает на входе значение текущего контекста, функцию которую надо выполнить interface Joiner<T> : where T is IHaveContext<T>
{
IHaveContext<T> Join(IHaveContext<T> currentContext, Action step);
}
// реализация интерфейса. Тоже тупа до безобразияclass ТруЪJoinier<T> : Joiner<T>
{
IHaveContext<T> Join(currentContext, step)
{
if(currentContext == true)
// намек на то, что функция, может получить текущий контекстvar res = step(first)
return res;
else
return false as IHaveContext;
}
}
// А теперь наш код из предыдущего примера в более пригодном для употребления видеvar joiner = new ТруЪJoiner();
// Да, я в курсе, что тут напутано с типами, и количеством параметров. Важна описываемая идея, а не код
joiner.Join(true,SomeWierdOperationThatSucceeds).Join(AnotherUgluSuccessOperation).Join(AndThisOperaiontFails);
Выглядит симпатишнее чем простыня ифов.
Что еще можно сделать на основе этих вещей. В смысле что может быть контекстом. НУ например слой логики, куда мы хотим подключить логирование.
Мы просто дергаем метод ЛОГ у логгера, а он уже сам узнает в каком контексте мы выполняемся, какие настройки логирования(дебаг, релиз) и прочие вещи,
абсолютно не интересные.
А можно сделать те же контексты аля транзакции, но чтобы они работали по фолсу, а не по ТруЪ.
для этого достаточно заменитть
var joiner = new ТруЪJoiner();
на
var joiner = new FalseJoiner();
А можно при парсинге протягивать контекс типа количество ошибко, текущая строка, текущий символ, текущая лексема.
Здравствуйте, gandjustas, Вы писали:
G>Это как раз просто, меня интересует код связывания. Под отладчиком я вижу что и как происходит, но осознать мозгом почему так работает получается у меня с большим трудом.
Код связывания? Вы про то, как работает bind?
Так же как в Linq каждый SelectMany обязан возвращать IEnumerable<T>, тут все селекторы возвращают StateMonad — некое вычисление, получающее состояние и возвращающее пару — состояние и контент:
G> var m = from s in StateMonad.Get<int>()
G> from _ in StateMonad.Put(s + 1)
G> from r in StateMonad.Return(0 /*dummy arg*/, Tr.Lf(new Scp<int, T>(s, leaf.Content)))
G> select r;
Каждый SelectMany оборачивает полученный StateMonad в другой StateMonad...
Получается цепочка дёргающих друг друга делегатов, передающих друг другу по цепочке State-content pair.
G> public static StateMonad<S, C2> SelectMany<S, C1, C2>(this StateMonad<S, C1> m, Func<C1, StateMonad<S, C2>> selector)
G> {
G> return new StateMonad<S, C2>(s =>
G> {
G> var scp = m.S2Scp(s);
G> return selector(scp.Content).S2Scp(scp.State);
G> });
G> }
То есть логика связывания — вернуть такой StateMonad (обёрнутый делегат), который:
при получении State-content пары вызовет вычисление m, передав эту пару, в результате получится новая пара. Потом вызовет селектор, передав контент новой пары, селектор вернёт вторую StateMonad, её вычислит с новой парой и возратит пару.
То есть по сути — объединили StateMonad и (вычисление, возвращающее StateMonad), получив новый StateMonad...
Здравствуйте, lomeo, Вы писали:
L>Здравствуйте, gandjustas, Вы писали:
G>>Кто-нибудь может объяснить как оно работает?
L>А что именно непонятно? Как работает State монада или как работает именно эта реализация State монады?
Конекретно меня интересует как протягивается этот самый state черезер каскад из лямбда-функций
Здравствуйте, Mirrorer, Вы писали:
M>Здравствуйте, gandjustas, Вы писали:
M>Ну, вот так как-то.
Да не, я понимаю что такое монады и как работает разметка дерева.
Меня интересует как работает state monad, в частности каким образом протягивается state через каскад лямбда функций.
Объяснение Бекмана из видео не вставило, а после просмотра отладчиком стало еще запутаннее.
Здравствуйте, gandjustas, Вы писали:
G>Меня интересует как работает state monad, в частности каким образом протягивается state через каскад лямбда функций.
Ну из бинда всё ясно же:
G> return new StateMonad<S, C2>(s =>
G> {
G> var scp = m.S2Scp(s);
G> return selector(scp.Content).S2Scp(scp.State);
G> });
Состояние уходит в первое вычисление (m), оттуда возвращается новое состояние (в паре), которое уходит во второе вычисление (возвращённое селектором) и возвращается новое состояние (тоже в паре). То есть после композиции биндом получается одно вычисление, получающее стэйт, пропускающее его через два вычисления и возвращающее результирующий стэйт...
G>Объяснение Бекмана из видео не вставило, а после просмотра отладчиком стало еще запутаннее.
В этом видео самоё клёвое, что проводится параллель между >>= и композицией
Ни в одном туториале по монадам прям явно в это носом не тычут...
p.s. Вам не мешает куча аннотаций типов? На F# всё же намного приятнее такие вещи изучать, computation expressions понятнее выглядят:
open System
type State<'a,'s> = State of ('s -> 'a * 's)
type StateBuilder() =
(* 'a -> M<'a> *)
member b.Return(a) =
State (fun s -> a, s)
(* M<'a> * ('a -> M<'b>) -> M<'b> *)
member b.Bind((State m), g) =
State (fun s ->
let (a, s') = m s in
let (State f') = g a in f' s')
let getState = State (fun s -> s, s)
let setState s = State (fun _ -> (), s)
let Execute (State f) s = let x,_ = f s in x
let state = StateBuilder()
(*******************************************)type Node<'a> =
| Branch of 'a Node * 'a Node
| Leaf of 'a
member node.Show(ident) =
String(' ', ident) |> printf "%s"match node with
| Leaf(x) -> printfn "Leaf: %A" x
| Branch(a,b) -> printfn "Branch:"
a.Show(ident+2)
b.Show(ident+2)
let rec labelMonad = function
| Leaf(x) ->
state { let! s = getState
do! setState (s+1)
return Leaf(x,s) }
| Branch(a,b) ->
state { let! l = labelMonad a
let! r = labelMonad b
return Branch(l,r) }
let tree =
Branch(
Branch(
Leaf 1,
Branch(Leaf 2, Leaf 3)),
Leaf 4);
tree.Show(0)
let m = labelMonad tree
let res = Execute m 0
res.Show(0)
Здравствуйте, Пельмешко, Вы писали:
П>Здравствуйте, gandjustas, Вы писали:
G>>Меня интересует как работает state monad, в частности каким образом протягивается state через каскад лямбда функций.
П>Ну из бинда всё ясно же: П>
G>> return new StateMonad<S, C2>(s =>
G>> {
G>> var scp = m.S2Scp(s);
G>> return selector(scp.Content).S2Scp(scp.State);
G>> });
П>
П>Состояние уходит в первое вычисление (m), оттуда возвращается новое состояние (в паре), которое уходит во второе вычисление (возвращённое селектором) и возвращается новое состояние (тоже в паре). То есть после композиции биндом получается одно вычисление, получающее стэйт, пропускающее его через два вычисления и возвращающее результирующий стэйт...
Порвало мозг... *Где здесь стреляющийся смайлик?*
G>>Объяснение Бекмана из видео не вставило, а после просмотра отладчиком стало еще запутаннее.
П>В этом видео самоё клёвое, что проводится параллель между >>= и композицией П>Ни в одном туториале по монадам прям явно в это носом не тычут...
Дык теория категорий.
В упор не могу понять:
П>let setState s = State (fun _ -> (), s)
setState — чистая функция. П>let rec labelMonad = function П> | Leaf(x) -> П> state { let! s = getState П> do! setState (s+1) // тут мы игнорим значение этой функции. П> return Leaf(x,s) } П> | Branch(a,b) -> П> state { let! l = labelMonad a П> let! r = labelMonad b П> return Branch(l,r) } П>[/ocaml]
так откуда всплывает новое состояние??
ТОже самое в исходном сообщении:
var m = from s in StateMonad.Get<int>()
from _ in StateMonad.Put(s + 1) // игнорируется значениеfrom r in StateMonad.Return(0 /*dummy arg*/, Tr.Lf(new Scp<int, T>(s, leaf.Content)))
select r;
Здравствуйте, Jack128, Вы писали:
J>Здравствуйте, Пельмешко, Вы писали:
J>В упор не могу понять:
П>>let setState s = State (fun _ -> (), s)
П>>let rec labelMonad = function
П>> | Leaf(x) ->
П>> state { let! s = getState
П>> do! setState (s+1) // тут мы игнорим значение этой функции.
П>> return Leaf(x,s) }
П>> | Branch(a,b) ->
П>> state { let! l = labelMonad a
П>> let! r = labelMonad b
П>> return Branch(l,r) }
П>>
В F#
do! expr in cexpr
дешугарится в:
b.Bind(expr,(fun () -> «cexpr»))
обратите внимание, значение expr не игнорируется, а уходит в бинд!
J>так откуда всплывает новое состояние?? J>ТОже самое в исходном сообщении:
J>
J> var m = from s in StateMonad.Get<int>()
J> from _ in StateMonad.Put(s + 1) // игнорируется значение
J> from r in StateMonad.Return(0 /*dummy arg*/, Tr.Lf(new Scp<int, T>(s, leaf.Content)))
J> select r;
J>
J>где, где блин сохраняется состояние????
Состояние проходит через все вычисления закулисами, в бинде, его можно геттером выдрать напоказ и присвоить контенту:
from s in StateMonad.Get<int>()
А потом замкнуться на это значение сеттером (это не само состояние, это выражение передающееся между вычислениями), который может менять значение настоящего состояния.
Здравствуйте, Jack128, Вы писали: J>Здравствуйте, Пельмешко, Вы писали: П>>Здравствуйте, Jack128, Вы писали: П>>В F# П>>
do! expr in cexpr
П>>дешугарится в: П>>
b.Bind(expr,(fun () -> «cexpr»))
П>>обратите внимание, значение expr не игнорируется, а уходит в бинд! J>угу, вроде проясняется что то. J>Вопрос по синтаксису, что означает запись state { expr } ?
Это computation expression, аналог do-нотации в хаскеле
Грубо говоря эта запись означает "преобразовать expr в вызовы методов экземпляра класса-builder'а — state (экземпляр класса StateBuilder)".
Здравствуйте, Пельмешко, Вы писали:
J>>Вопрос по синтаксису, что означает запись state { expr } ?
П>Это computation expression, аналог do-нотации в хаскеле П>Грубо говоря эта запись означает "преобразовать expr в вызовы методов экземпляра класса-builder'а — state (экземпляр класса StateBuilder)".
А ты не мог бы преобразовать labelMonad в код без этой нотации??
Здравствуйте, 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))))
Обратите внимание, что обращение к s в возврате Leaf(x,s) — это замыкание на параметр внешней лямбды...
В таком виде ещё лучше видно, что состояние проходит все лямбды в бинде.
getState умеет доставать значение состояния и передавать в параметр следующей лямбды, при этом состояние не меняется.
setState может любое значение, на которое можно замкнуться, записать в новое состояние, просто вернув в бинд новое состояние.
Здравствуйте, Пельмешко, Вы писали:
П>Здравствуйте, 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))))
П>
П>Обратите внимание, что обращение к s в возврате Leaf(x,s) — это замыкание на параметр внешней лямбды...
П>В таком виде ещё лучше видно, что состояние проходит все лямбды в бинде. П>getState умеет доставать значение состояния и передавать в параметр следующей лямбды, при этом состояние не меняется. П>setState может любое значение, на которое можно замкнуться, записать в новое состояние, просто вернув в бинд новое состояние.
Отличная идея, надо desugar_ить LINQ в C# варианте и развернуть Get и Put чтобы понятнее было как передается state
Здравствуйте, gandjustas, Вы писали:
G>Отличная идея, надо desugar_ить LINQ в C# варианте и развернуть Get и Put чтобы понятнее было как передается state
Вот так оно дешугарится, ну почти:
static StateMonad<int, Tr<Scp<int,T>>> GetLabelMonad<T>(Tr<T> tree)
{
if (tree is Lf<T>)
{
var leaf = tree as Lf<T>;
var m =
StateMonad.Get<int>().SelectMany(s =>
StateMonad.Put(s + 1).SelectMany(_ =>
StateMonad.Return(0, Tr.Lf(new Scp<int, T>(s, leaf.Content)))));
return m;
}
else if(tree is Br<T>)
{
var br = tree as Br<T>;
var m =
GetLabelMonad(br.Left).SelectMany(l =>
GetLabelMonad(br.Right).SelectMany(r =>
StateMonad.Return(0, Tr.Br(l, r))));
return m;
}
else
{
throw new Exception("Invalid object type");
}
}
В этом варианте не нужен Select и ещё одна перегрузка SelectMany, они нужны только из-за особенностей query-синтаксиса...