Skip to content
Hallway
0:00 / 0:00

#doublylinkedlist#fingertrees#deque

Implementing Doubly Linked Lists in Haskell

NYC Haskell User's Group

1.7K subscribers • 23 videos on Hallway

YouTube
  • Recommended by 4 people: 4 in engineering communities.
  • Presented by Brian Hurt, software engineer

Advanced. Deep dive for people who know the field.

6.8K views11 years ago4 recommendations

Programming languagesComputer scienceHaskellData structuresAlgorithms

Brian Hurt explains the challenges of implementing doubly linked lists in Haskell and presents functional alternatives like deques and finger trees.

New York Haskell Users Group, November 13, 2014 Implementing Doubly Linked Lists in Haskell by Brian Hurt Haskell poses several unique problems in implementing the standard doubly linked list data structure. I show the major problems Haskell has, and explain not one, but two different solutions to the problem (for those who already know the answer, yes it's deques I'm talking about). Basic knowledge of Haskell (simple type classes, variant types and pattern matching) is assumed, as well as some familiarity with doubly linked lists in other languages. Brian Hurt has been a professional software engineer for 20 years now (quite a feat for someone who still claims to be 29 years old), originally in device drivers and embedded work, but more recently in functional programming languages and databases. He has been paid to program in OCaml, Clojure, and assembly language, as well as a number of other programming languages (including Java, C++, and C). To his dismay, he doesn't have any professional Haskell experience, but has been learning it for the past several years. He is currently working at kloud.co, which is a still stealth-mode start up (although they're hoping to change that soon).

Why it's here

4 people recommend this

What people say. Recommended as an excellent explanation of how to implement and reason about purely functional double-ended queues and finger trees.

Moments people linked to

u/mightybytein r/haskell • Recommends

Implementing Doubly Linked Lists in Haskell
12View on Reddit

u/sclvin r/haskell • Recommends

On “[NYHUG] The Not-A-Wat in Haskell”

That's Brian Hurt, and he gives talks at NY Haskell fairly often. Here's one on Monad Transformers and lifting exception handling and the like: link to this video Here's one on doubly ended queues in haskell (and fingertrees for that matter): link to this video And here's one on type inference: link to this video (and here's an old talk on the benefits of static typing: https://vimeo.com/72870631)
7View on Reddit

u/dukerutledgein r/haskell • Recommends

On “How to approach implementing imperative algorithms functionally?”

Brian Hurt gave a nice talk on implementing doubly linked lists which touches on imperative algos in functional languages: link to this video
3View on Reddit

u/gelisamin r/haskell • Recommends

On “Can I build up a [(Char, Seq Int)] without blowing up memory/time?”

Isn't appending amortized O(1)? Documentation claiming it's O(1) A video explaining why
3View on Reddit

u/gelisamin r/haskell • Recommends

On “Can I build up a [(Char, Seq Int)] without blowing up memory/time?”

Seq only needs 3 extra words of memory per element, and it's easy to make a variant which takes only 2 or even less (video explanation). How many extra words does the thunk representation use?
1View on Reddit