Dyadic Decomposition using Functional lenses by Eduardo Lemos

April 10, 2024

In the presentation Making Imperative Functional: Dyadic Decomposition by Eduardo Lemos, Eduardo shares his background in functional programming and introduces dyadic decomposition as a method for compressing large 3D data objects, such as point clouds, using functional programming techniques. He explains the need for compressing point clouds due to their immense size and discusses the dyadic decomposition approach, which involves recursively slicing the point cloud into smaller cubes and creating a binary tree where each parent node points to its immediate two children. The real compression happens in the next step, where silhouettes are created, and bits are saved by exploiting the relationship between the parent node and its children. The speaker also discusses the importance of combining forms in functional programming languages and shares his experience of being introduced to functional programming through a course, which led him to focus on it for his graduation project and current master’s research.

Making Imperative Functional: Dyadic Decomposition: A comprehensive overview

Eduardo Lemos’ background in functional programming dates back to his high school days and spans various languages including Haskell. With a deep understanding of functional programming, Eduardo aims to simplify complex concepts like dyadic decomposition through functional lenses.

 

The concept of dyadic decomposition

Eduardo introduced dyadic decomposition using point clouds as an example. Point clouds, large 3D data objects used in applications like autonomous cars and 3D mapping, need compression due to their massive size. Traditional methods like the OCT tree involve recursively slicing the point cloud into smaller cubes. Dyadic decomposition, however, uses a similar recursive slicing but focuses on creating binary trees where each node points to its immediate children. This method not only serves as an intermediary step but also sets the stage for efficient, lossless compression by leveraging the relationships between parent and child nodes.

 

Practical Implementation and Compression Techniques

Eduardo illustrated the practical steps of dyadic decomposition. By reading a 2D silhouette image with a mask, the relationship between parent and child nodes can be exploited to save bits in data transmission. For instance, if a parent node indicates the presence of certain pixels, and the left child node does not contain them, these pixels must be on the right child node. This method creates a binary tree of slices of the original point cloud, which are then mapped to silhouettes and folded into binary payloads.

 

Building the triforce data structure

The triforce data structure, a binary tree of binary trees, was another highlight of Eduardo’s presentation. This structure efficiently exploits the relationships between nodes, facilitating immutable data handling. Eduardo explained the PC2 Triforce function, which transforms a point cloud axis into a sparse Triforce tree, and demonstrated the use of Haskell’s functional programming capabilities, such as fmap and composition operators, to manipulate these trees.

 

Functional programming concepts in action

Eduardo’s presentation showcased the power of functional programming in handling complex tasks. He mapped the Triforce data structure to binary, applied masking processes, and folded the structures together using functions like map and fold. This process produced a bitstream, demonstrating how functional programming can be effectively used for compression algorithms. While the implementation may not be the most efficient, it clearly illustrates the potential of functional programming in converting imperative tasks.

 

Exploring combining forms and mathematical abstractions

Eduardo also explored the idea of borrowing combining forms from various domains, including mathematics, to enhance programming abstractions. Concepts like fusion laws for foldr and the fixpoint combinator can provide more powerful programming abstractions. He discussed the redundancy in diagrams and the need for masking processes, illustrating the depth and versatility of functional programming.

 

Personal journey and invitation to learn

Eduardo shared his journey into functional programming, from initial skepticism to making it the focus of his academic research. His project, which formed the basis of the presentation, is a testament to his dedication and passion for the field. He invited the audience to join his computer science study group for further discussions and exploration of interesting projects and programming languages.

 

Conclusion

Eduardo Lemos’ presentation on dyadic decomposition provided a comprehensive look at how functional programming can transform and simplify complex tasks. By leveraging functional programming principles and techniques, Eduardo demonstrated the practical applications and potential of these concepts in real-world scenarios. His insights and methods offer valuable lessons for anyone interested in advancing their understanding and application of functional programming.

 

Additional resources

Check out more from the MeetUp Func Prog Sweden. Func Prog Sweden is the community for anyone interested in functional programming. At the MeetUps the community explore different functional languages like Erlang, Elixir, Haskell, Scala, Clojure, OCaml, F# and more.