Reddit Reddit reviews Purely Functional Data Structures

We found 34 Reddit comments about Purely Functional Data Structures. Here are the top ones, ranked by their Reddit score.

Computers & Technology
Books
Databases & Big Data
Data Modeling & Design
Purely Functional Data Structures
Used Book in Good Condition
Check price on Amazon

34 Reddit comments about Purely Functional Data Structures:

u/dons · 38 pointsr/programming

The darcs people (and the pure FP world) have been talking about the similarities between persistant structures, transactional memory and rollback, and revision control for years, FWIW. Good to see these ideas becoming more widespread.

E.g. here's a similar, older triple:

  • tcache, database+persistance based on STM
  • darcs, flexible dvcs based on (true) immutable patches (no rebase)
  • haskell, typed, pure-by-default functional language with the first built-in STM

    and I'll throw in NixOS, a Linux package manager based on immutable packages.

    This is what the FP revolution looks like, I guess.
u/itkovian · 20 pointsr/haskell

I can highly recommend Okasaki's book on data structures: https://www.amazon.com/Purely-Functional-Data-Structures-Okasaki/dp/0521663504, if you are looking for inspiration or techniques.

u/edwardkmett · 17 pointsr/programming

Three books that come to mind:

Types And Programming Languages by Benjamin Pierce covers the ins and outs of Damas-Milner-style type inference, and how to build the bulk of a compiler. Moreover, it talks about why certain extensions to type systems yield type systems that are not inferrable, or worse may not terminate. It is very useful in that it helps you shape an understanding to understand what can be done by the compiler.

Purely Functional Data Structures by Chris Okasaki covers how to do things efficiently in a purely functional (lazy or strict) setting and how to reason about asymptotics in that setting. Given the 'functional programming is the way of the future' mindset that pervades the industry, its a good idea to explore and understand how to reason in this way.

Introduction to Algorithms by Cormen et al. covers a ton of imperative algorithms in pretty good detail and serves as a great toolbox for when you aren't sure what tool you need.

That should total out to around $250.

u/45g · 16 pointsr/programming

You are repeating yourself and your position is inconsistent. You acknowledge the usefulness of generic types and functions and yet you claim it is enough to have a fixed set of those. How come there was a need for them in the first place? Why does Go need the generic functionality it already has? What if somebody wants to implement something from Purely Functional Data Structures for example? What if i need a singly linked list? Your point is I should have many of them. One per type. This is plain ridiculous. For one it precludes the possibility of putting this into libraries which is to say it goes directly against re-use. If you fail to see that I feel sorry for you.

u/joshuaeckroth · 16 pointsr/compsci

To my knowledge, Chris Okasaki made a big impact with this work in this area, and directly influenced Clojure, among other projects.

His book is a great read: http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504

It's based on his PhD thesis: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

This StackOverflow question addresses what's changed since the late 90's: http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki

u/jozefg · 12 pointsr/programming

I'd suggest

  1. Learn You a Haskell For Great Good
  2. Real World Haskell (Though some parts are a bit dated)
  3. Parallel and Concurrent Programming in Haskell
  4. Purely Functional Datastructures

    Now past this it's not entirely clear where to go, it's much more based on what you're interested in. For web stuff there's Yesod and it's associated literature. It's also around this time where reading some good Haskell blogs is pretty helpful. In no particular order, some of my favorites are

  5. A Neighbourhood of Infinity
  6. Haskell For All
  7. Yesod/Snoyman's blog
  8. Edward Kmett's stuff on FPComplete
  9. Edward Yang's blog
  10. Lindsey Kuper's blog

    And many, many more.

    Also, if you discovery type theory is interesting to you, there's a whole host of books to dig into on that, my personal favorite introduction is currently PFPL.
u/queensnake · 11 pointsr/programming

Thanks much, I appreciate that.

edit: Note, all, the one book I've seen on this.

u/cabbagerat · 10 pointsr/compsci

Start with a good algorithms book like Introduction to algorithms. You'll also want a good discrete math text. Concrete Mathematics is one that I like, but there are several great alternatives. If you are learning new math, pick up The Princeton Companion To Mathematics, which is a great reference to have around if you find yourself with a gap in your knowledge. Not a seminal text in theoretical CS, but certain to expand your mind, is Purely functional data structures.

On the practice side, pick up a copy of The C programming language. Not only is K&R a classic text, and a great read, it really set the tone for the way that programming has been taught and learned ever since. I also highly recommend Elements of Programming.

Also, since you mention Papadimitriou, take a look at Logicomix.

u/atium_ · 9 pointsr/haskell

Not what you are asking for really, but you'll get better with experience.


Take a few imperative algorithms and convert them over.
Solve some problems on HackerRank. Do it your way, afterwards compare your solution with some of the other Haskell solutions.


Some functional algorithms and data structures are done very differently. Chris Okasaki has a book Purely Functional Data Structures that covers some (though its for ML)


There are papers/articles on topics such as Functional Binomial Queues and Hinze has got a paper on Priority Search Queues that also covers an implementation of Dijkstra and Prims.


The Haskell Wiki has got a page listing functional pearls. Maybe also take a look at how dynamic programming and such paradigms are done functionally.

For most algorithms you can write it in a imperative manner and use mutation and looping constructs, if you have to. But you aren't going to find some guide to convert any algorithm into idiomatic Haskell. Some functional implementations require you to think differently.

u/snatchinvader · 7 pointsr/haskell

A good book describing similar techniques for designing and implementing efficient data structures with lazy evaluation is Purely Functional Data Structures.

u/bhrgunatha · 7 pointsr/compsci

This isn't criticism or a judgment, but that sounds like an odd request. If you've really absorbed what's in CLRS, I would imagine you could just research those data structures yourself and, for example, look at some open source implementations.

Or research what's in other Data Structures and Algorithms books and read up on them.

Having said that - there is an MIT course on advanced data structures.

I also enjoyed Chris Okasaki's Purely Functional Data Structures

There are 2 Coursera courses in particular - Princeton University's Algorithms Part I and Algorithms Part II - they've provided a web site for their book where lots of algorithms and data structures are implemented using Java with the libraries and source code freely available.

u/kqr · 6 pointsr/haskell

This is a completely unhelpful answer, but if you're looking to get to know the things you listed under not comfortable, there is

u/PM_ME_UR_OBSIDIAN · 4 pointsr/programming

You'll find your answers in this book. Great both as a tutorial and a reference.

The TL;DR version is that with a bit of cleverness you can use redundancy in your data structures to save time and memory. For example, naively implementing a purely functional stack is easy peasy. Just take an immutable linked list; all stack operations are O(1) time and space.

u/[deleted] · 4 pointsr/programming

I know exactly what you're talking about. When things aren't mutable, you can do clever optimizations that allow sharing and reuse of objects already in memory. There is a pretty good book on this, and the author has a free pdf you can read too.

u/RedDeckWins · 4 pointsr/Clojure

I would highly recommend reading Purely Functional Data Structures.

Right now it only works with numbers. If you utilized compare you could make it more generalized.

u/gfixler · 3 pointsr/haskell

>When working in Java you just need to embrace it.

Haha. Agreed. When you're a hostage, just do what they say, and live to fight another day.

>...showed me how it's supposed to be done.

I've tried to see how it's supposed to be done many times, but it's just a broken abstraction for me. If I want to turn off a light, I flip the switch to off. In OOP, I'm supposed to create a Light class to hold the state of everything related to the light, then accessor methods with access control levels set up just so to protect me from the world, in case anyone wants to make something based on my whole lighting setup. Then I need to create nouns to shepherd my verbs around, like LightSwitchToggleAccessor, and worry about interfaces and implementations and design patterns.

In Haskell I'd say "A light can just be on or off; let's make it an alias for a boolean."

type Light = Bool

I want to be able to turn it on and off; that's just a morphism from Light state to Light state.

toggleLight :: Light -> Light
toggleLight = not

And that's it. If I realize later that I don't want Light and Bool to be interchangeable, I'd just make Light it's own type with a simple tweak to give it its own two states:

data Light = Lit | Unlit

And change the toggle to match:

toggleLight :: Light -> Light
toggleLight Lit = Unlit
toggleLight Unlit = Lit

Then I could toggle a big list of lights:

map toggleLight [light1, light2, mainLight, ...]

Or turn them all on:

map (const Lit) [light1, light2, ...]

I have equational reasoning. I can do like-for-like transformations. I get all the goodness of category theoretic abstractions, giving me reusability the likes of which I've never seen in OOP (not even close). Etc.

>objects are closures

Closures are immutable (hence the glory of this). Objects tend to be mutable, which is a nightmare (every day where I work in C#).

>try to keep as much stuff pure as possible

But you just have no way of knowing what's pure and what isn't in any of the OOP environments I've seen, and it is so obvious in C# at work; it plagues us constantly - new bugs daily, and projects always slow tremendously as they grow, and things become unchangeable, because they're too ossified. Just that small thing, that need to specify effects in your types, makes it so much easier to reason about what actually goes on in a function. For example, my Lights up there actually can't do anything in the world. I know that because of their "Light -> Light" types. All they can do is tweak data, the same way every single time they're called - you can replace them with table lookups. They'd have to get some kind of IO markup in their types before they could change anything, which is part of that equational, deterministic reasoning that makes FP so easy to understand, even as projects grow.

I don't want to try to do things. I want it to be fun to do what's good, and impossible to do what's bad. The goal of a great type system is to "make illegal states impossible to represent." I made it impossible to mess with the world, and so I can know with 100% certainty what toggleLights does. I quite literally cannot know what the same function would do in C#. It could return a different result every time. Multiply that up to a few 100klocs, and I have no idea how our projects work, and no idea what I'm breaking when I push commits (and I often break things, and everyone else constantly breaks my stuff, because we can't properly reason about anything).

u/panicClark · 3 pointsr/ItalyInformatica

Io lavoro come sviluppatore ormai da diversi anni, anch'io non laureato (o meglio, laureato lo sarei, ma in un ambito piuttosto distante dall'informatica).

Le difficoltà maggiori all'inizio le ho incontrate quando si trattava di andare un pelino oltre al "giocare col lego" con linguaggi e framework (rigorosamente di alto livello): i fondamentali di come funzionano le reti e i protocolli, le strutture dati e gli algoritmi. Il primo ambito sto ancora cercando di approfondirlo bene, per strutture dati e algoritmi all'epoca mi consigliarono Introduction to Algorithms e devo dire che mi ci sono trovato abbastanza bene, seppure l'ho trovato noioso da seguire.

Mi è tornato relativamente più utile approfondire i linguaggi funzionali. Il classico in tal senso è Purely Functional Data Structures, ma a me è piaciuto di più Functional Programming in Scala.

u/yeahbutbut · 3 pointsr/programming

> If you can spare the ram and computing time, sure. This also exists in OOP under the name of Memento pattern but is hardly ever applied because of how slow it can be with big data sets.

The advantage with immutable data structures is that your "modifications" are stored as a delta from the original so the memory requirements are fairly low. [0][1] You probably would have plenty of ram to spare.

>`How do you write the following in FP, with a single stack

(def graph (atom #{ #_"vertices go here"}))
(def stack (atom (list)))

(let [some-value 42.0]
(def my-command {:do (fn [graph] (map #(merge %1 {:length (+ (:length %1) some-value)} graph)
:undo (fn [graph] (map #(merge %1 {:length (- (:length %1) some-value)} graph)})

(defn apply-command [cmd]
;; replace the graph with a version mutated by do
(swap! graph (:do cmd))
;; put the undo function on the stack
(swap! stack conj (partial swap! graph (:undo cmd))))

(defn undo-last []
(swap! stack
(fn [stack]
;; run the undo fn
((first stack))
;; return the stack sans the top element
(rest stack))))

(apply-command my-command)
(clojure.pprint/pprint @graph)
(undo-last)
(clojure.pprint/pprint @graph)

But you probably wouldn't have the graph as a global atom, someValue would be injected into the command, etc, etc.

[0] https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504/ref=sr_1_1?ie=UTF8&qid=1493603954&sr=8-1&keywords=purely+functional+data+structures

[1] http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice.html

Edit: formatting, do was + undo was - in the original, add usage at the end

u/Mason-B · 2 pointsr/programming

An immutable list is implemented as described by the other responses, but equivalent immutable data structures exist for all mutable data structures. Immutable arrays with O(1) lookup and O(1) 'assignment', which of course enables O(1) dictionaries. And all the others.

This talk by Rich Hikley, creator of Clojure, has a good example of how it works (About 23 minutes in, but the rest of the talk is good). Also see Purely Functional Structures for an indepth look at it, and many more.

u/stulove · 2 pointsr/compsci

On the functional programming front, Purely Functional Data Structures has some fun stuff in it. You should be really familiar with functional languages before going through it though.

u/nekochanwork · 2 pointsr/learnprogramming

Expert F# 4.0 by Dom Syme (creator of F#) is a useful reference for people who already have OO programming experience, but want to learn FP. It's also a .NET language, so it interops with C# with minimal effort.

The F# Wikibook is a little dated, but otherwise a useful free reference for people learning F# for the first time.

Purely Functional Data Structures by Chris Okasaki is still the best reference available for data modeling. It uses SML as it's reference language, but almost all of the examples can be converted to equivalent F#, Haskell, or Scala.

u/jdh30 · 2 pointsr/rust

> To be honest I don't entirely understand the term "functional data structure" I'm sort of new to functional programming myself.

I'm sure you're familiar with the idea of an immutable int or double or even string. Purely functional data structures just extend this idea to collections like lists, arrays, sets, maps, stacks, queues, dictionaries and so on. Whereas operations on mutable collections take the operation and collection and return nothing, operations on purely functional data structures return a new data structure.

Here's an example signature for a mutable set:

val empty : unit -> Set<'a>
val contains : 'a -> Set<'a> -> bool
val add : 'a -> Set<'a> -> unit
val remove : 'a -> Set<'a> -> unit

and here is the equivalent for a purely functional set:

val empty : Set<'a>
val contains : 'a -> Set<'a> -> bool
val add : 'a -> Set<'a> -> Set<'a>
val remove : 'a -> Set<'a> -> Set<'a>

Note that empty is now just a value rather than a function (because you cannot mutate it!) and add and remove return new sets.

The advantages of purely functional data structures are:

  • Makes it much easier to reason about programs because even collections never get mutated.
  • Backtracking in logic programming is a no-brainer: just reuse the old version of a collection.
  • Free infinite undo buffers because all old versions can be recorded.
  • Better incrementality so shorter pauses in low latency programs.
  • No more "this collection was mutated while you were iterating it" problems.

    The disadvantages are:

  • Can result in more verbose code, e.g. graph algorithms often require a lot more code.
  • Can be much slower than mutable collections. For example, there is no fast purely functional dictionary data structure: they are all ~10x slower than a decent hash table.

    The obvious solution is to copy the entire input data structure but it turns out it can be done much more efficiently than that. In particular, if all collections are balanced trees then almost every imaginable operation can be done in O(log n) time complexity.

    Chris Okasaki's PhD thesis that was turned into a book is the standard monograph on the subject.

    In practice, purely functional APIs are perhaps the most useful application of purely functional data structures. For example, you can give whole collections to "alien" code safe in the knowledge that your own copy cannot be mutated.

    If you want to get started with purely functional data structures just dick around with lists in OCaml or F#. Create a little list:

    > let xs = [2;3];;
    val int list = [2; 3]

    create a couple of new lists by prepending different values onto the original list:

    > list ys = 5::xs;;
    val int list = [5; 2; 3]

    > list zs = 6::xs;;
    val int list = [6; 2; 3]

    > xs;;
    val int list = [2; 3]

    Note how prepending 5 onto xs didn't alter xs so it could still be reused even after ys had operated on it.

    You might also want to check out my Benefits of OCaml web page. I'd love to see the symbolic manipulation and interpreter examples translated into Rust!

    > Personally I used Atom for a while, until I learned how to use Vim, now I use that. IDE information for Rust can be found at https://areweideyet.com/

    Excellent. I'll check it out, thanks.
u/NLeCompte_functional · 2 pointsr/haskell

I have not read Functional Programming In Scala so I am unsure of the scope.

But Purely Functional Data Structures is a classic: https://www.amazon.com/Purely-Functional-Data-Structures-Okasaki/dp/0521663504


It's largely focused on SML, but all the examples are also given in Haskell. And for learning Haskell (or Scala/F#/Agda/etc), porting the SML examples is a good exercise.

u/htedream · 2 pointsr/Clojure

most of the algorithms books are for any programming language as long as they are imperative.

as far as functional languages go, there are:

u/mozilla_kmc · 1 pointr/rust

> FWIW, a persistent data structure is somewhat orthogonal to laziness.

But you do need lazy evaluation (in-place update of thunks, whether that's provided by the language or a library) to get amortized time guarantees on persistent data structures. How much this matters in practice, I do not know.

u/loup-vaillant · 1 pointr/programming

> That's not an experiment, it's an anecdote about a thing that happened once.

It's a whole class, taught by a not exactly nobody professor. If it was one student, that would be anecdotal. But this is a sizeable sample, bordering on "statistically significant". As for "happened once", I'm sure he taught several other similar classes since then. Maybe we should ask him how it went?

A better argument than the worn out "anecdote", is to suspect the evidence to be filtered, one way or the other. I presented the argument to counter some point I believed false, but nothing guarantees that I didn't know of, and omitted, arguments to the contrary. (There are many reasons why I may do so, included but not limited to self deception, dishonesty, conflict of interest…) I will just hereby swear that I do not recall having ever encountered evidence that mandatory indentation was either detrimental, or neutral to the learning of programming languages. Trust me, or don't.

> And it's an anecdote about introducing absolute novices to programming.

It was their second language. I assume they programmed for at least a semester.

> Even if it were an experiment, experiments don't provide arguments, they provide data to use to test arguments.

Experiments provide evidence for or against hypothesises. Pointing out "hey, look at this experiment that crushes your beliefs flat!" is the argument. Which may have flaws besides the experiment itself (the results of the experiment may have to crush my beliefs flat, and I misread the paper). </pedantic>

---

> And even if this were an experiment with a result compatible with an argument about indentation, there's no reason to think that this would have any bearing on infix expression shenanigans in Lisp.

I agree. Yes, you have read that correctly, I agree. <Sardonic smile…>

There is something I suspect you and many others in this thread have totally missed: sweet expressions are not just about infix expressions. That's a detail. The crux of sweet expression is actually significant indentation. Here:

define (factorial n)
if (<= n 1)
1
(* n (factorial (- n 1)))

I don't like the last line (too many parentheses). Let's try this:

define (factorial n)
if (<= n 1)
1

  • n
    factorial (- n 1)

    So, while results about indentation doesn't have any bearing about infix notation, it does have direct bearing about sweet expressions as a whole.

    > You're pretty sloppy when you address something that seems to support your position, aren't you?

    You just deserve my smug smile :-D
u/rocksInGorges · 1 pointr/compsci

From personal experience:
CLRS (theory)
http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 (data structures / practical)

From what everyone else says:
wizard book.

u/DeusExCochina · 1 pointr/Clojure

Heh, I'm not about to! I don't even try to understand the other Purely Functional Data Structures - it's all black magic to me. But you're right - that doubly linked lists map so poorly onto immutable structures is no doubt a very strong reason we're not seeing them there.

u/mreiland · 1 pointr/rust

immutable data can cause problems with data structures and the like, here's a book on the topic.

http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504?ie=UTF8&*Version*=1&*entries*=0

u/artsrc · 0 pointsr/programming

Can't you get laziness with a function pointer (in a thunk struct perhaps) in any language from C up? Having it as the default is a syntactic convenience?

What are doubly linked lists really useful for? What about having two singly linked lists in opposite orders?

Would you start by buying this book?

http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504

I tend to use sets, maps, queues (priority, fifo), and lists (indexed and singly linked).