Реализация стека, очереди и дека на языке F# в функциональном стиле

[vba]

Спасибо за статью, у меня вопрос немного не по теме. Подскажите пожалуйста как на F# реализовать утиную типизацию? На Scala это все выглядит очень просто:

def inTheForest(duck: { def quack; def feathers }) = {
  duck.quack
  duck.feathers
}

Заранее спасибо.

[danslapman]

Вот так можно:

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)

[danslapman]

Накосячил с отступами, корректный вариант такой:

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)

[vba]

Спасибо,

А вы не подскажете для чего в конце (^a : (member Count: int) arg) стоит arg? Мне не совсем ясна семантика. До него все понятно, это как в scala, тип ^a, у которого есть свойство Count типа int, но вот зачем тут arg? Заранее вам благодарен.

[danslapman]

Здесь

^a : (member Count: int)

мы как-бы получаем поле в виде метода, а затем передаём ему «аргумент» — конкретный экземпляр.

Здесь между Scala и F# существенное различие: в Scala будет произведена лишь проверка во время компиляции, во время выполнения же вызовы будут осуществляться через рефлексию, в F# же для каждого конкретного типа будет сгенерирована перегрузка.

[vba]

Все понял, спасибо за пояснение.

[danslapman]

Пожалуйста)

[onikiychuka]

Вы пытаетесь писать на функциональном языке как на императивном — используя наиболее низкоуровневые концепции языка. Имхо — это стандартная ошибка новичков. Если так хочется сделать все через список (а не ввести свой тип данных на котором эти операции будут действительно работать оптимально), то лучше использовать высокоуровневые примитивы типа fold для этих задач. Там как минимум будет оптимизация tail call будет. Вообще написание своих собственных рекурсивных функций на стандартные типы данных — это антипаттерн для функциональных языков.
Да кстати стандартный pop (вытаскивание элемента из стека или очереди) вполне решается вот такой функцией:

let pop stk =
 match stk with
 |[] -> (None, [])
 |hd :: tail -> (Some(hd), tail)

и использовать ее можно вот так:

let (res, rest) = pop stk

[nickolaym]

Иммутабельный список — не самая удачная структура данных для очереди и дека. Очевидно, что или запись, или изъятие (а то и запись, и изъятие) происходят через полное копирование. Это и O(n) памяти, и O(n) времени.

Предлагаю заглянуть в книгу Криса Окасаки, который посвятил функциональным структурам данных свою диссертацию.
www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Тем более, что он пишет на другом диалекте ML — а именно, SML, так что перепереть на F# труда не составит.

Заворачивать head и pop в монаду мейби (она же эмэлевская option) — на вкус и цвет. При наличии обычных функций проверки — необязательно; точнее, пусть оно кидает ошибки.

[Vitter]

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

Что касается Дека и очереди — ваша реализация — это операции 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

[ProPupil]

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