Comments 11
Спасибо за статью, у меня вопрос немного не по теме. Подскажите пожалуйста как на F# реализовать утиную типизацию? На Scala это все выглядит очень просто:
Заранее спасибо.
def inTheForest(duck: { def quack; def feathers }) = {
duck.quack
duck.feathers
}
Заранее спасибо.
Вот так можно:
let inline getLen arg =
(^a : (member Count: int) arg)
let ra = ResizeArray<string>()
let rl = Dictionary<string, string>()
printfn "%i" (getLen ra)
printfn "%i" (getLen rl)
Накосячил с отступами, корректный вариант такой:
let inline getLen arg =
(^a : (member Count: int) arg)
let ra = ResizeArray<string>()
let rl = Dictionary<string, string>()
printfn "%i" (getLen ra)
printfn "%i" (getLen rl)
Спасибо,
А вы не подскажете для чего в конце
А вы не подскажете для чего в конце
(^a : (member Count: int) arg) стоит arg? Мне не совсем ясна семантика. До него все понятно, это как в scala, тип ^a, у которого есть свойство Count типа int, но вот зачем тут arg? Заранее вам благодарен.Здесь
мы как-бы получаем поле в виде метода, а затем передаём ему «аргумент» — конкретный экземпляр.
Здесь между Scala и F# существенное различие: в Scala будет произведена лишь проверка во время компиляции, во время выполнения же вызовы будут осуществляться через рефлексию, в F# же для каждого конкретного типа будет сгенерирована перегрузка.
^a : (member Count: int)
мы как-бы получаем поле в виде метода, а затем передаём ему «аргумент» — конкретный экземпляр.
Здесь между Scala и F# существенное различие: в Scala будет произведена лишь проверка во время компиляции, во время выполнения же вызовы будут осуществляться через рефлексию, в F# же для каждого конкретного типа будет сгенерирована перегрузка.
Вы пытаетесь писать на функциональном языке как на императивном — используя наиболее низкоуровневые концепции языка. Имхо — это стандартная ошибка новичков. Если так хочется сделать все через список (а не ввести свой тип данных на котором эти операции будут действительно работать оптимально), то лучше использовать высокоуровневые примитивы типа fold для этих задач. Там как минимум будет оптимизация tail call будет. Вообще написание своих собственных рекурсивных функций на стандартные типы данных — это антипаттерн для функциональных языков.
Да кстати стандартный pop (вытаскивание элемента из стека или очереди) вполне решается вот такой функцией:
и использовать ее можно вот так:
Да кстати стандартный pop (вытаскивание элемента из стека или очереди) вполне решается вот такой функцией:
let pop stk =
match stk with
|[] -> (None, [])
|hd :: tail -> (Some(hd), tail)
и использовать ее можно вот так:
let (res, rest) = pop stk
Иммутабельный список — не самая удачная структура данных для очереди и дека. Очевидно, что или запись, или изъятие (а то и запись, и изъятие) происходят через полное копирование. Это и O(n) памяти, и O(n) времени.
Предлагаю заглянуть в книгу Криса Окасаки, который посвятил функциональным структурам данных свою диссертацию.
www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Тем более, что он пишет на другом диалекте ML — а именно, SML, так что перепереть на F# труда не составит.
Заворачивать head и pop в монаду мейби (она же эмэлевская option) — на вкус и цвет. При наличии обычных функций проверки — необязательно; точнее, пусть оно кидает ошибки.
Предлагаю заглянуть в книгу Криса Окасаки, который посвятил функциональным структурам данных свою диссертацию.
www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Тем более, что он пишет на другом диалекте ML — а именно, SML, так что перепереть на F# труда не составит.
Заворачивать head и pop в монаду мейби (она же эмэлевская option) — на вкус и цвет. При наличии обычных функций проверки — необязательно; точнее, пусть оно кидает ошибки.
Не совсем понятно, зачем понадобилось делать стек, ибо большинство стандартных функций для работы со списками уже подходят.
Что касается Дека и очереди — ваша реализация — это операции O(n) — а значит, совершенно не подходят.
К счастью, есть структура, которая может работать O(1) с добавлением и в начало и в конец структуры — это пальчиковые деревья (Finger_tree)
Вот, например, её реализация на Хаскеле:
Data-Sequence
Ну, а далее реализация дека (да и очереди) проще простого:
Что касается Дека и очереди — ваша реализация — это операции O(n) — а значит, совершенно не подходят.
К счастью, есть структура, которая может работать O(1) с добавлением и в начало и в конец структуры — это пальчиковые деревья (Finger_tree)
Вот, например, её реализация на Хаскеле:
Data-Sequence
Ну, а далее реализация дека (да и очереди) проще простого:
import Data.Sequence
type Deq = Seq
pushDBegin :: Deq a -> a -> Deq a
pushDBegin deq el = el <| deq
pushDEnd deq el = deq |> el
popDBegin :: Deq a -> (Maybe a, Deq a)
popDBegin = hd . viewr
where
hd EmptyR = (Nothing, empty)
hd (tl :> a) = (Just a, tl)
popDEnd = hd . viewl
where
hd EmptyL = (Nothing, empty)
hd (a :< tl) = (Just a, tl)
type Que = Seq
pushQ :: Que a -> a -> Que a
pushQ = pushDEnd
popQ :: Que a -> (Maybe a, Que a)
popQ = popDBegin
Sign up to leave a comment.
Реализация стека, очереди и дека на языке F# в функциональном стиле