?

Log in

No account? Create an account
Красно-чорное дерево в несколько строчек: - kouzdra [entries|archive|friends|userinfo]
kouzdra

[ website | www.kouzdra.org ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Красно-чорное дерево в несколько строчек: [Oct. 17th, 2015|03:11 pm]
kouzdra
Меня тут приятель спросил - так вот

let balance = function
    Black, z, Node (Red, y, Node (Red, x, a, b), c), d
  | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
  | Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
  | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) -> Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
  | a, b, c, d -> Node (a, b, c, d)
LinkReply

Comments:
From: anonim_legion
2015-10-17 03:55 pm (UTC)
И так же, как с квиксортом на хаскеле, в библиотеках для промышленного применения так никто не делает.
(Reply) (Thread)
[User Picture]From: kouzdra
2015-10-18 12:52 pm (UTC)
Для промприменения вообще вылизывают в стандартных алгоритамх битики и тактики - но обычно этого не делают - потому что простота и сопровождаемость бьет

Я скажем сортировку всегда писал по шеллу - не потому что она очень хороша - а потому что я ее писать умею - а ее качество достаточное
(Reply) (Parent) (Thread)
From: (Anonymous)
2015-10-17 09:05 pm (UTC)
Кстати, можете пояснить за то, какой язык стоит учить --
Standard ML или Ocaml? И практически, и на идейном (теоретическом) уровне.

И что из литературы-книжек можно почитать?
Ну, кроме выложенных курсов и т.п.?
(Reply) (Thread)
[User Picture]From: kouzdra
2015-10-18 04:39 pm (UTC)
На теоритическом уровне пофиг - вот на практиеском лучше окамль. SML именно что слишком теоритечен
(Reply) (Parent) (Thread)
From: (Anonymous)
2015-10-19 02:44 pm (UTC)
Спасибо!
(Reply) (Parent) (Thread)
[User Picture]From: polytheme
2015-10-21 12:35 am (UTC)
есть же ещё F# :)
(Reply) (Parent) (Thread)
From: tristes_tigres
2015-10-21 09:49 pm (UTC)
А вот если, скажем, немного играл в Хаскель, то какую функциональщину может иметь смысл получить для работы? F# или какую-нибудь Closure?
(Reply) (Parent) (Thread)
[User Picture]From: rdia
2015-10-19 04:07 am (UTC)
Так для OCaml'а есть просто самоучитель (ocaml-ora-book.pdf) - читаете его и выполняете указания. Сперва будет ломка, если это первый функциональный, потом пойдёт хорошо.

Ещё см. http://ocaml.org/learn/books.html (скачивать с bookfi или аналогичных)

И, возможно это лучше посмотреть с самого начала - http://ocaml.org/docs/cheat_sheets.html
(Reply) (Parent) (Thread)
From: (Anonymous)
2015-10-19 02:46 pm (UTC)
Спасибо!
(Reply) (Parent) (Thread)
[User Picture]From: _winnie
2015-11-04 10:48 pm (UTC)
Как обычно, функцию удаления показать постеснялись. А она в три раза сложнее добавления, и чуть сложнее ложится на иммутабельность. Например, функция удаления отсюда со своими под-функциями выглядит так - http://pastebin.com/yr0Sixm1

Плюс самая вкусная штука, которую не замечают другие авторы RB-tree (например в википедии), это вот эта - "where each of the four input cases is mapped to the same output case", которая относится не к языку, и можно использовать в любом языке.


Edited at 2015-11-04 10:54 pm (UTC)
(Reply) (Thread)
[User Picture]From: _winnie
2015-11-04 11:07 pm (UTC)
> Плюс самая вкусная штука, которую не замечают другие авторы RB-tree (например в википедии), это вот эта - "where each of the four input cases is mapped to the same output case"

Я понял, это действительно похоже на модельный красивый квик-сорт, который для практики лучше не использовать.
Вот такое дерево:
       Bz     
      /  \    
     Ry  d
    /  \      
  Rx   c      
 /  \         
a    b        

у авторов этой статьи превращается в такое:
     Ry
    /  \
  Bx    Bz
 / \   / \
a   b c   d


Хотя лучше его превратить в такое (просто перекрасить), и избежать потенциального конфликта красный-красный на уровне выше:
       Rz
      /  \    
     By   d
    /  \      
  Rx   c      
 /  \         
a    b


(Reply) (Parent) (Thread)