Purely functional data structures demystified

schedule 01:30 PM - 01:30 PM place Grand Ball Room 1

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 

 
43 favorite thumb_down thumb_up 4 comments visibility_off  Remove from Watchlist visibility  Add to Watchlist
 

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

schedule Submitted 3 years ago

Comments Subscribe to Comments

comment Comment on this Proposal
  • Jatin
    By Jatin  ~  3 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  ~  3 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  ~  3 years ago
    reply Reply

    is this beginner level talk or advanced?

    • Mohit Thatte
      By Mohit Thatte  ~  3 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.


  • Liked Morten Kromberg
    keyboard_arrow_down

    Morten Kromberg - Pragmatic Functional Programming using Dyalog

    Morten Kromberg
    Morten Kromberg
    CXO
    Dyalog
    schedule 3 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.

  • Liked Keith Bennett
    keyboard_arrow_down

    Keith Bennett - Functional Programming in Ruby

    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

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

    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

    Debasish Ghosh - Property based testing for functional domain models

    Debasish Ghosh
    Debasish Ghosh
    Consultant
    IRadix Inc
    schedule 3 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.

  • Liked Dhaval Dalal
    keyboard_arrow_down

    Dhaval Dalal / Ryan Lemmer - Code Jugalbandi

    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.

  • Liked Mushtaq Ahmed
    keyboard_arrow_down

    Mushtaq Ahmed - Demystify the Reactive Jargons

    Mushtaq Ahmed
    Mushtaq Ahmed
    Mr Scala
    ThoughtWorks
    schedule 3 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.

  • Liked Ramakrishnan Muthukrishnan
    keyboard_arrow_down

    Ramakrishnan Muthukrishnan - An introduction to Continuation Passing Style (CPS)

    60 mins
    Tutorial
    Intermediate

    Traditionally functions return some value. Someone is waiting for that value and does some computation with it. This "someone" is called the continuation of this value. In a normal functional call, the continuation is "implicit". In the "continuation passing style" (hence forth called with the short form, CPS), we make the continuations explicit. In this style, function definitions take an extra argument called "continuation" and it never return. The "return value" of the function 'continues' by passing this value as an argument to the continuation. Continuations are sometimes called "gotos with arguments".

    CPS is used as an intermediate stage while compiling a program since it makes the control structure of the program explicit and hence can be converted easily to machine code. Another feature of a CPS-transformed function is that it is tail-recursive even if the original function was not written in a tail-recursive style.

    Continuations enable a programmer to build new control operators (if the language's built-in operators does not already provide the control operators the programmer need).

  • 90 mins
    Tutorial
    Beginner

    Code used during the talk: https://github.com/shashi/fuconf-talk
    Slides: https://docs.google.com/presentation/d/16Xfqd-xU8y2JEN0TIcacDoYnp0b5-W7ESDB5v1SmcXs/edit#slide=id.p

     

    Elm is a strongly typed functional reactive programming (FRP) language that compiles to HTML, CSS, and Javascript. In Elm, the Signal type represents a time-varying value--things like mouse position, keys pressed, current time are signals. With Signals, one can write terse code that is isomorphic to a dataflow diagram of the app. The code hence feels natural and is 100% callback free. All this, with powerful type inference.

    This talk is an introduction to FRP. It explores functionally composing graphics and UIs, and creating interactions and animations with the Signal type. There will also be an overview of Elm’s execution mechanism and the time traveling debugger: a consequence of Elm's purely functional approach.

    While instructive, it will be good fun too, in the spirit of Elm.

  • Liked Vagmi Mudumbai
    keyboard_arrow_down

    Vagmi Mudumbai - Clojurescript and Om - Pragmatic functional programming in the Javascript Land

    Vagmi Mudumbai
    Vagmi Mudumbai
    schedule 3 years ago
    Sold Out!
    60 mins
    Demonstration
    Beginner

    Javascript programmers have had a lot of choices when it comes to programming. There were days of mootools, scriptaculous and jQuery and then there are now days of Angular, Ember, Knockout and the like. As a javascript programmer myself, I find that Clojurescript/React as Om offers a fresh perspective into building performant Javascript UIs that are easy to write.

    The talk will introduced concepts of React, immutable datastructures in Clojure and live code an application that demonstrates the concepts.

     

  • Liked Bhasker Kode
    keyboard_arrow_down

    Bhasker Kode - Writing and improving tail recursive functions

    Bhasker Kode
    Bhasker Kode
    Building stuff
    Helpshift
    schedule 3 years ago
    Sold Out!
    45 mins
    Talk
    Beginner

    Brief history of recursion 

    Snippets from a few languages

    What is tail recursion?

    Design choices around recursion

    The importance of tail recursion in erlang

    How do you profile such improvements?

     

     

     

  • Liked Rahul Goma Phulore
    keyboard_arrow_down

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

    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

  • Liked Venkat Subramaniam
    keyboard_arrow_down

    Venkat Subramaniam - Haskell for Everyday Programmers

    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 Aditya Godbole
    keyboard_arrow_down

    Aditya Godbole - Learning (from) Haskell - An experience report

    Aditya Godbole
    Aditya Godbole
    CTO
    Vertis Microsystems
    schedule 3 years ago
    Sold Out!
    45 mins
    Experience Report
    Beginner

    Functional programming as a programming style and discipline is useful even in languages which are not pure functional languages. By practising programming in a pure functional language like Haskell, programmers can drastically improve the quality of code when coding in other languages as well.

    The talk is based on first hand experience of using Haskell in internal courses in our organisation to improve code quality.

    This talk will cover Gofer (one of the earliest variants of Haskell) as a teaching tool, including the choice of the language, the features from Haskell that should (and shouldn't) be covered and the obstacles and benefits of the exercise.

     

  • Liked Venkat Subramaniam
    keyboard_arrow_down

    Venkat Subramaniam - Keynote: The Joy of Functional Programming

    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

    Rahul Goma Phulore - Promise of a better future

    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 Anuj
    keyboard_arrow_down

    Anuj - Embedded Erlang : Experiments with the BeagleBone Black

    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.

  • Liked Anil Wadghule
    keyboard_arrow_down

    Anil Wadghule - SOLID: the next step is Functional

    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.

  • Liked Shakthi Kannan
    keyboard_arrow_down

    Shakthi Kannan - Lambdaaaaaaaaaa Calculus

    Shakthi Kannan
    Shakthi Kannan
    DevOps Engineer
    Self
    schedule 3 years ago
    Sold Out!
    60 mins
    Talk
    Beginner

    This talk is an introduction on lambda calculus and will address the foundations of functional programming languages.

    We will learn the building blocks of lambda calculus - syntax, rules, and application.

  • Liked Rahul Goma Phulore
    keyboard_arrow_down

    Rahul Goma Phulore - You could have invented monads!

    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!

  • Liked Venkat Subramaniam
    keyboard_arrow_down

    Venkat Subramaniam - Designing with Lambda Expressions in Java

    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.