Purely functional data structures demystified

Immutable, persistent data structures form a big part of the value proposition of most functional programming languages.

It is important to understand why these data structures are useful and how they make it easier to reason about your program. 

It is also instructive to see how these data structures are implemented to get a greater appreciation for the inherent tradeoffs between performance and immutability.

In this talk I will do a walkthrough of some of these data structures drawing from the work of Chris Okasaki[1], and attempt to explain the essential ideas in a simple way. 


[1] Purely Functional Data Structures, Chris Okasaki, School of Computer Science, Carnegie Mellon University 

 
 

Outline/structure of the Session

I will broadly structure the talk as below:

- meaning of immutability and persistence, where we define terms

- the value and the tradeoffs that come with immutability and persistence, where we understand the Why?

- the essential ideas behind some of the data structures, where we understand the What?

- if time permits, implementations in some functional languages, where he understand the How?

I will use animations and pictures to clarify the conceptual model behind these ideas. Thereby attempting to "demystify" the topic.

Learning Outcome

- The value of immutability

- A deeper understanding of how some data structures are implemented in functional languages including asymptotic complexity analysis.

- An appreciation of how functional languages are able to compete with imperative languages on performance in spite of having tougher constraints.

- References to literature for further study

Target Audience

Programmers interested in data structures, algorithms, complexity analysis

Requirements

Participants should be conversant with basic data structures and analysis of algorithms.

schedule Submitted 2 years ago

Comments Subscribe to Comments

comment Comment on this Proposal
  • Jatin
    By Jatin  ~  2 years ago
    reply Reply

    Hello. I think it is a fantastic topic.

    Can you specify more on what data structure implementation's you would be covering. Secondly on what language will it be? It would be really interesting on how pure languages do it (Scala though provides many funcational data structures but does a lot of imperative activity internally). You can probably provide some pure implementations in a well-known language.

  • Debasish Ghosh
    By Debasish Ghosh  ~  2 years ago
    reply Reply

    Which language will you use for discussing the data structures ? Will it be ML or Haskell or any other language like (may be) Scala ?

    Also to understand the time complexity of these data structures, I guess the audience also needs to be familiar with concepts like amortization, lazy evaluation, call by need etc. So I think it will be a fairly advanced talk.

  • vimalk
    By vimalk  ~  2 years ago
    reply Reply

    is this beginner level talk or advanced?

    • Mohit Thatte
      By Mohit Thatte  ~  2 years ago
      reply Reply

      I'd like it to be accessible to beginners. But I will assume some level of familiarity with basic data structures and analysis of algorithms.


  • Morten Kromberg
    Morten Kromberg
    schedule 2 years ago
    Sold Out!
    60 mins
    Demonstration
    Beginner

    APL is a member of the family of languages that are approaching middle age (Ken Iverson’s book titled “A Programming Language” was published in 1962). APL was very influential in the 60’s and 70’s, and widely used to deliver “end user computing” - but although the REPL, dynamic scope and lack of a type system endeared APL to domain experts, it also drew fire from computer scientists, most famously when Edsger Dijkstra declared that “APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past it creates a new generation of coding bums.”

    Dyalog is a modern, array-first, multi-paradigm programming language, which supports functional, object-oriented and imperative programming based on an APL language kernel. Dyalog allows people with good ideas – from bright high school students to PhDs – to contribute directly to the software development process using a notation which fits comfortably with those used in their own domains. Subject matter experts can write prototypes or, with suitable training and/or support, highly efficient, parallel and robust code that can be embedded in high-performance production applications.

  • Venkat Subramaniam
    Venkat Subramaniam
    schedule 2 years ago
    Sold Out!
    60 mins
    Keynote
    Intermediate

    It's been around for a long time, but everyone's talking about it all of a sudden. But why and why now? We've been

    programming in languages like Java for a while, quite well. Now we're asked to change and the languages themselves

    are changing towards this style of programming. In this keynote, a passionate polyglot programmer and author of

    "Functional Programming in Java: Harnessing the Power of Java 8 Lambda Expressions" will share the reasons

    we need to make the paradigm shift and the pure joy—the benefits—we will reap from it.

  • Liked Rahul Goma Phulore
    keyboard_arrow_down

    Getting into the mind of a Haskeller

    Rahul Goma Phulore
    Rahul Goma Phulore
    schedule 2 years ago
    Sold Out!
    45 mins
    Talk
    Intermediate

    You have probably heard of this mysterious language called Haskell. The Haskell code typically looks very different from what we are used to from other languages. The Haskell discussions and blogs mainly seem to center around types and some algebra stuff. Many attempting to learn the language find it befuddling to the point that they give up early in exasperation.

    In this talk, I will take you into the mind of a typical Haskeller, and show you how she thinks about programs; how the holy trinity of types, functions, and algebras form the basis of all program design; how this leads to natural evolution of computational abstractions such as monads; how types can sometimes even “write” your programs for you; and how Haskellers manage to sleep more peacefully at night than most of us do!

  • Liked Rahul Goma Phulore
    keyboard_arrow_down

    Object-functional programming: Beautiful unification or a kitchen sink?

    Rahul Goma Phulore
    Rahul Goma Phulore
    schedule 2 years ago
    Sold Out!
    60 mins
    Talk
    Advanced

    Scala began its life as an experiment to “unify” object-oriented programming and functional programming. Martin Odersky believed that the differences between FP and OO are more cultural than technical, and that there was a room for beautifully unify various ideas from the two into one simple core.

    How successful has Scala been in its goals? Is it the like “the grand unified theory of universe” or like the infamous “vegetarian ham”? [1]

    In this talk, we will see just how Scala unifies various ideas – such as type-classes, algebraic data types, first-class modules, functions under one simple core comprising of traits, objects, implicits, and open recursion. We will how this unification unintendedly subsumes many concepts that require seprate features in other languages, such as functional dependencies, type families, GADTs in Haskell. We will see how this has given a rise to a new “implicit calculus”, which could lay a foundation for next generation of generic programming techniques.

    We will see that this unification comes at a certain cost, wherein it leads to some compromises on both sides. However many of these trade-offs are particular to Scala (largely due to the JVM imposed restrictions). The goal of unification is still noble, and we need not throw the baby out with the bathwater.

    [1]: https://twitter.com/bos31337/status/425524860345778176

  • Rahul Goma Phulore
    Rahul Goma Phulore
    schedule 2 years ago
    Sold Out!
    45 mins
    Talk
    Intermediate

    Futures and promises are no strangers to most programmers. They have made their way into major mainstream languages, including but not limited to, Java, C#, JavaScript, and C++.

    This abstraction however is typically dreaded due to the way they’re typically done. Most manifestations lead to the insidious callback hell, and some, like Java’s, are incredulously limited.

    Why can’t we keep our simple, straightforward code, and still have the concurrency benefits of futures and promises?! Turns out we can. Functional programming is here to the rescue! We will see how the seemingly obscure abstractions like monads, delimited continuations allow us to do just that.

    We will also go over some syntactic-transformation based approaches (basically, macros), such as C#’s async-await, and see how it compares with the functional approaches discussed earlier.

  • Liked Rahul Goma Phulore
    keyboard_arrow_down

    You could have invented monads!

    Rahul Goma Phulore
    Rahul Goma Phulore
    schedule 2 years ago
    Sold Out!
    45 mins
    Tutorial
    Intermediate

    Of all the computational abstractions that functional programming has brought to the table, monads seem to be disproportionately more popular than the rest. (Or should I say, notorious?) The web is filled with monad tutorials, ranging from those using pure mathematics to explain the idea, to those using (half-baked) metaphors like burritos and space-suites. One might think this should make it relatively easy to grok monads. Unfortunately, many of these tutorials do a rather poor job, and do not help students gain an intuition for the idea. This has resulted in an unparalleled FUD around monads.

    A part of difficulty people have when learning functional programming abstractions such as monads comes from the fact that, this new way of thinking involves looking for abstraction opportunities in places they’re not used to.

    In this talk, I will start by presenting some seemingly unrelated day-to-day code examples. I will underline the problems common to all of them, and then we will all together derive a general abstraction applicable to all of them. If you can follow through till the last bit (and in my experience, most of the audience does), you have not only understood but essentially re-invented monads!

  • Bodil Stokke
    Bodil Stokke
    schedule 2 years ago
    Sold Out!
    45 mins
    Talk
    Beginner

    The programming paradigms that served us so well through the 80s and 90s are failing us. Building systems the way we're used to building them always seems to end in the inevitable death march towards exponential complexity. But once you stop to ask the right question- "what's really causing all this complexity?" - you realise the answers have really been staring you in the face all along. Debugging is only hard when you can't reason about your code. Concurrency is only hard when you can't predict the state of your code. Reusability is only hard when your components aren't naturally composable.

    Fortunately, languages addressing these issues specifically are popping up all over the place. In many cases, it turns out we've had the solutions to our problems for a long time, we've just forgotten about them, or never really bothered to look. Let's take a moment to explore some of these languages, not as exercises in syntactic details, but looking at the inherent properties in their design that enable us to defy decades of OO tradition and write honest-to-Dijkstra bug free, fault tolerant software without even trying. After half a century in the wilderness, functional programming seems to finally be gaining some ground on the barbarians. Let's examine why.

  • Bodil Stokke
    Bodil Stokke
    schedule 2 years ago
    Sold Out!
    60 mins
    Keynote
    Beginner

    In this talk, we'll explore why some technologies end up inexplicably dominating our field while others fade away despite their obvious merits. What will it take for the languages we care about to succeed, and what are the consequences of success? Let's apply a broad perspective to the mess we've made of modern computer science, and explore our options for getting the situation back on track through a careful examination of history, science and ponies.

  • Liked Amit Dev
    keyboard_arrow_down

    A practical introduction to Monads

    Amit Dev
    Amit Dev
    schedule 2 years ago
    Sold Out!
    30 mins
    Demonstration
    Beginner

    Some people find it hard to understand Monads (like pointers in C). But it is actually a simple concept (like pointers in C). In this session we try to understand Monads and why they are useful through examples. It is purely from a practical point of view and no theory is covered.

  • Liked Venkat Subramaniam
    keyboard_arrow_down

    Haskell for Everyday Programmers

    Venkat Subramaniam
    Venkat Subramaniam
    schedule 2 years ago
    Sold Out!
    90 mins
    Talk
    Intermediate

    I learn different languages not to make use of them, but to program in my current languages in a better way. As we adapt functional style of programming in mainstream languages, like Java, C#, and C++, we can learn a great deal from a language that is touted as a purely functional language.

    Haskell is statically typed, but not in a way like Java, C#, or C++. Its static typing does not get in the way of productivity. Haskell quietly does lazy evaluation and enforces functional purity for greater good. Everyday programmers, like your humble speaker, who predominantly code in mainstream languages, can greatly benefit from learning the idioms and style of this elegant language. The next time we sit down to crank out some code in just about any language, we can make use of some of those styles, within the confines of the languages, and move towards a better, functional style.

  • Liked Venkat Subramaniam
    keyboard_arrow_down

    Designing with Lambda Expressions in Java

    Venkat Subramaniam
    Venkat Subramaniam
    schedule 2 years ago
    Sold Out!
    90 mins
    Talk
    Intermediate

    As Java programmers we have used a number of design patterns and design techniques. With the introduction of lambda expressions, we now have some more sharper tools in our design toolbox. Come to this presentation to learn how we can implement some elegant design ideas with lambda expressions. We will learn about these design techniques, not using diagrams, but by realizing the ideas in code.

  • Liked Anuj
    keyboard_arrow_down

    Embedded Erlang : Experiments with the BeagleBone Black

    Anuj
    Anuj
    schedule 2 years ago
    Sold Out!
    45 mins
    Demonstration
    Intermediate

    There is a close similiarity in the way which embedded systems are developed, and the paradigms involved in functional programming. 

    Error's will ALWAYS occur & The system must NEVER go down

    With the rise of homebrewed 3D printing, UAVs and IoT, the need for creating a robust programming environment is more than ever. It becomes close to impossible for casual dabblers to take their ideas to a level beyond the "maker"ware.

    In this talk, I will be talking about different efforts under embedded Erlang. There will be a demo on the process involved in building a simple application i.e. LED blink. I will then show the key highlights of a slightly more complicated application, and then how one would go about designing an embedded application.

    Perhaps it's too early to tell, but I think something like the Nerves Project is the answer here. We need a community driven platform for creating great embedded applications using Erlang.

  • Mushtaq Ahmed
    Mushtaq Ahmed
    schedule 2 years ago
    Sold Out!
    60 mins
    Tutorial
    Intermediate

    Haskell has populairzed typelcasses a principled way to add ad-hoc extensions on existing data types. They allow you to 1) add new operations on existing data types and 2) support new data types on existing operations, and thus solve the famous "expression problem".

    There is a lot of similarily between typeclasses and Java good practices of programming to interfaces and preferring composition over inheritance. The missing link is the implicit dictionary passing which allows haskell to be much more concise and expressive.

    In this tutorial, we will look at how Scala adopts typeclasses by adding the missing link of implicits.

  • Liked Keith Bennett
    keyboard_arrow_down

    Functional Programming in Ruby

    Keith Bennett
    Keith Bennett
    schedule 2 years ago
    Sold Out!
    45 mins
    Talk
    Beginner

    Although Ruby is not known as a functional language, it does support higher order functions in the form of lambdas and procs. Ruby's support for both object oriented and functional approaches, along with its conciseness, clarity, and expressiveness, make it an excellent choice as a general purpose programming language.

    This session, geared toward the functional novice, shows how to implement functional approaches in Ruby, and shows why you would want to.

    Topics covered will include:

    • in testing, using lambdas to verify that certain behaviors do or do not not raise errors
    • lambdas as predicates
    • deferred execution
    • composite functions
    • nested functions
    • using lambdas to hide variables
    • functions that return functions (partial application, currying)
    • lightweight event handling
    • chaining behavior with lambda arrays
    • how lambdas differ from conventional Ruby methods
  • Liked Ryan Lemmer
    keyboard_arrow_down

    Realtime Distributed computing: dealing with Time and Failure in the wild

    Ryan Lemmer
    Ryan Lemmer
    schedule 2 years ago
    Sold Out!
    45 mins
    Experience Report
    Intermediate

    There is a growing need for scalable, realtime business systems that are continuously running and highly-available. Two very different frameworks/approaches you could use to build such systems are Storm and Akka.

    Systems created with Storm or Akka are distributed, at runtime, on as many machines as you choose. The inherent concurrency implied by this brings the issues of State, Time and Failure into sharp focus. Functional programming has much to say about dealing with state and time; not surprisingly, both Storm and Akka have strong roots in functional languages (for Storm it is Clojure, and for Akka, Scala).

    In this talk we'll explore the core concepts and challenges of distributed computation; the role of functional programming in concurrent distributed computing; we'll take a look at Storm and Akka, by example, and see that as different as these 2 approaches are, the underlying difficulties of distributed computation remains evident in both: dealing with time, and dealing with failure.

  • Liked Debasish Ghosh
    keyboard_arrow_down

    Property based testing for functional domain models

    Debasish Ghosh
    Debasish Ghosh
    schedule 2 years ago
    Sold Out!
    45 mins
    Talk
    Intermediate

    Manual testing is something that's error prone, incomplete and impossible to replicate on a large scale. We have instead been using xUnit style of testing for quite some time now. This approach has a number of drawbacks like (a) We need to write test cases by hand which again doesn't scale for large systems (b) We may miss out some of the edge cases (c) Safeguarding missing cases with coverage metrics doesn't help, since metrics are mostly based on heuristics (d) maintaining test cases and test data is a real pain.

    In property based testing we write properties and not low level test cases. And let the system generate test cases which validate such properties. There are 2 main advantages with this approach:

    1. You think in terms of properties (or specifications) of the domain model which is the right granularity to think about
    2. You don't need to manage test cases, which is completely done by the system that generates a large collection of test data

    This approach is ideal for the functional programming paradigm, which focuses on pure functions. Using functional programming it's easier to reason about your model - hence it's easier to test functional programs using properties. In this talk I will take some real world examples of property validation and verification using scalacheck (the property based testing library for Scala) and a real world domain model.

  • Dhaval Dalal
    Dhaval Dalal
    Ryan Lemmer
    Ryan Lemmer
    schedule 2 years ago
    Sold Out!
    60 mins
    Demonstration
    Beginner

    In Indian classical music, we have Jugalbandi, where two lead musicians or vocalist engage in a playful competition. There is jugalbandi between Flutist and a Percussionist (say using Tabla as the instrument). Compositions rendered by flutist will be heard by the percussionist and will replay the same notes, but now on Tabla and vice-versa is also possible.

    In a similar way, we will perform Code Jugalbandi to see how the solution looks using different programming languages and paradigms.

    During the session, Dhaval and Ryan will take turns at coding the same problem using different languages and paradigms. There would be multiple such rounds during the Jugalbandi.

  • Mushtaq Ahmed
    Mushtaq Ahmed
    schedule 2 years ago
    Sold Out!
    60 mins
    Tutorial
    Beginner

    Objected oriented languages like Scala support the paradigm of programming with functions. How does it work? The language has to conceptually map functions to objects. This tutorial will explain this idea by starting with a simple Java-like code and progressively refactor it to make use of higher order functions. As a result, you will learn about a few syntax sugars and also the cost implication of using objects to represent functions.

  • Mushtaq Ahmed
    Mushtaq Ahmed
    schedule 2 years ago
    Sold Out!
    60 mins
    Demonstration
    Intermediate

    Sync, Async, Blocking, Non-Blocking, Streaming are the buzzwords in the reactive programming world. This talk will attempt to attach some meaning to them. It will also demo the performance and resource consumption patterns for blocking-io, Scala Futures and RxJava Observables for comparable programs. Finally, a command line application that consumes twitter streams API will demo what is possible using the new reactive abstractions.

  • Anil Wadghule
    Anil Wadghule
    schedule 2 years ago
    Sold Out!
    45 mins
    Talk
    Beginner

    As Object Oriented programmers, we follow SOLID Design Principles for improving OO design of our applications.

    If you take the SOLID principles to their extremes, you arrive at something that makes Functional Programming look quite attractive.

    Objects are merely a poor man's closures. And ultimately Closures are a poor man's objects.

    This talk explains about how applying SOLID Design principles like Single Responsibility Principle (SRP) leads to many small classes. Furthermore, if you rigorously apply the Interface Segregation Principle (ISP), you'll eventually arrive at the ultimate Role Interface: an interface with a single method.

    If you apply the SRP and ISP like that, you're likely to evolve a code base with many fine-grained classes that each have a single method.

    Objects are data with behaviour. Closures are too are data with behaviour.

    This talk will enlighten how applying Object Oriented Design Principles to their extreme will lead you to Functional Programming.

    It's necessary for Object Oriented programmer to understand why Functional programming makes sense.

    At the end, this talk will also cover essential basics of Functional programming needed to be known for every Object Oriented Programmer.