Skip to main content
Home

Main navigation

  • Home
  • Series
  • People
  • Depts & Colleges
  • Open Education

Main navigation

  • Home
  • Series
  • People
  • Depts & Colleges
  • Open Education

Generic Functional Parallel Algorithms: Scan and FFT

Series
International Conference on Functional Programming 2017
Video Embed
Conal Elliott, Target, USA United States, gives the third presentation in the second panel, Functional Programming Techniques, in the ICFP 2017 conference.
Parallel programming, whether imperative or functional, has long focused on arrays as the central data type. Meanwhile, typed functional programming has explored a variety of data types, including lists and various forms of trees. Generic functional programming decomposes these data types into a small set of fundamental building blocks: sum, product, composition, and their associated identities. Definitions over these few fundamental type constructions then automatically assemble into algorithms for an infinite set of data types--some familiar and some new. This paper presents generic functional formulations for two important and well-known classes of parallel algorithms: parallel scan (generalized prefix sum) and Fast Fourier Transform (FFT). Notably, arrays play no role in these formulations. Consequent benefits include a simpler and more compositional style, much use of common algebraic patterns--such as Functor, Applicative, Foldable, and Traversable--and freedom from possibility of run-time indexing errors. The functional generic style also clearly reveals deep commonality among what otherwise appears to be quite different algorithms. Instantiating the generic formulations to "top-down" and "bottom-up" trees as well as "bushes", two well-known algorithms for each of parallel scan and FFT naturally emerge, as well as two possibly new algorithms.

More in this series

View Series
International Conference on Functional Programming 2017

A Pretty But Not Greedy Printer (Functional Pearl)

Jean-Philippe Bernardy, University of Gothenburg, gives the second presentation in the second panel, Functional Programming Techniques, in the ICFP 2017 conference.
Previous
International Conference on Functional Programming 2017

A Unified Approach to Solving Seven Programming Problems (Functional Pearl)

William E. Byrd, University of Utah, USA, gives the fourth presentation in the second panel, Functional Programming Techniques, in the ICFP 2017 conference.
Next
Licence
Creative Commons Attribution-Non-Commercial-Share Alike 2.0 UK: England & Wales; http://creativecommons.org/licenses/by-nc-sa/2.0/uk/

Episode Information

Series
International Conference on Functional Programming 2017
People
Conal Elliott
Keywords
technology
computing
programming
Department: Department of Computer Science
Date Added: 12/12/2017
Duration: 00:19:01

Subscribe

Apple Podcast Video Video RSS Feed

Download

Download Video

Footer

  • About
  • Accessibility
  • Contribute
  • Copyright
  • Contact
  • Privacy
'Oxford Podcasts' Twitter Account @oxfordpodcasts | MediaPub Publishing Portal for Oxford Podcast Contributors | Upcoming Talks in Oxford | © 2011-2022 The University of Oxford