50

I have been trying to learn about functional programming, but I still struggle with thinking like a functional programmer. One such hangup is how one would implement index-heavy operations which rely strongly on loops/order-of-execution.

For example, consider the following Java code:

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(1,2,3,4,5,6,7,8,9);
        System.out.println("Nums:\t"+ nums);
        System.out.println("Prefix:\t"+prefixList(nums));
    }
  
    private static List<Integer> prefixList(List<Integer> nums){
      List<Integer> prefix = new ArrayList<>(nums);
      for(int i = 1; i < prefix.size(); ++i)
        prefix.set(i, prefix.get(i) + prefix.get(i-1));
      return prefix;
    }
}
/*
System.out: 
Nums:   [1, 2, 3, 4, 5, 6, 7, 8, 9]
Prefix: [1, 3, 6, 10, 15, 21, 28, 36, 45]
*/

Here, in the prefixList function, the nums list is first cloned, but then there is the iterative operation performed on it, where the value on index i relies on index i-1 (i.e. order of execution is required). Then this value is returned.

What would this look like in a functional language (Haskell, Lisp, etc.)? I have been learning about monads and think they may be relevant here, but my understanding is still not great.

5
  • 23
    As pointed out below, this is not an example where one really needs indices. Indeed, many common algorithms do not need indices. Still, some do: for instance, computing the sequence 0, a[0], a[a[0]], a[a[a[0]]], ... requires random access (beyond assuming all the elements are valid indices). In those rare circumstances, we resort to... arrays, e.g. Data.Vector. Haskell can be used imperatively, when needed -- we just rarely need to do so.
    – chi
    Mar 7, 2022 at 22:02
  • 3
    Is your question about implementing your algorithm in any functional language or specifically about only using ADTs (e.g. how Haskell's List is implemented as a linked list)? There are functional languages that have value types that are not ADTs, see Swift's Array or Haskell's Vector (mentioned above), while the latter does not support O(1) updating. Mar 8, 2022 at 13:55
  • 13
    Your implementation is already perfectly functional. prefixList() does not depend on any other data than is passed in its arguments and does not have any effect other than its return value. That's the essence of a pure function. Or course some languages make it easier to write functional code than others, I'd rate Java at about 4.5 out of 10 lambdas. Mar 8, 2022 at 13:58
  • 1
    @Feuermurmel My question was more so related to any algorithm than the prefix one I provided as an example. I am trying to learn how to apply the patterns of thinking to move away from always using indices.
    – AaronC
    Mar 9, 2022 at 23:17
  • @AaronC This is of course a fair objective, trying to implement algorithms on lists in terms of transformations of the whole list instead of explicitly accessing individual elements by index! It was the title that was bothering me because it's implying that functional languages per se can't handle index-based algorithms. Mar 11, 2022 at 21:22

8 Answers 8

59

Believe it or not, that function is actually built-in to Haskell.

> scanl (+) 0 [1..9]
[0,1,3,6,10,15,21,28,36,45]

So the broad answer is very often: There are convenient list-related primitives that we build up from rather than writing loops by hand. People like to say that recursion is the closest analogue in FP to "for loops" in imperative programming. While that may be true, the average functional program uses a lot less explicit recursion than the average imperative program uses for loops. Most of what we do (especially with lists) is built up of map, filter, foldl, and all of the other (highly-optimized) goodies in Data.List, Data.Foldable, Data.Traversable, and the rest of base.

As for how we implement those functions, you can look at the source for scanl. The one on GHC is written a bit differently for efficiency reasons, but the basic gist is this

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl _ q [] = [q]
scanl f a (b:xs) = a : scanl f (f a b) xs

You don't need indices. You need to keep track of the single previous value as you build the list, and we can do that with a function argument. If you genuinely do have an algorithm that needs random access to various indices, we have Data.Vector for that. But 99% of the time, the answer is "stop thinking about indices".

7
  • 14
    ' 99% of the time, the answer is "stop thinking about indices" ' is unrealistic. Many of the things people do with arrays in C / Python / Matlab etc. e.g. for simulation or data science can not be expressed feasibly with Haskell list operations. I still fully agree that arrays-with-indices obsession should be overcome, but it typically requires a bit more fundamental changes of thinking. cs.ox.ac.uk/seminars/2418.html Mar 8, 2022 at 12:17
  • 20
    @leftaroundabout I'd disagree. I'd say 99.5% of what people do with indices is mind-numbingly trivial to convert to non-index forms. The last 0.5% is indeed interesting, and worth paying attention to. Speaking from my experience and code that I have observed, its very rare that we are doing genuinely interesting things with indexes. most of the time its just boring looping over data in order. They're just so boring that we don't even notice we're doing them anymore. You are right, however, that that last 0.5% often requires a substantial fundamental change of perspective.
    – Cort Ammon
    Mar 9, 2022 at 16:25
  • 2
    @CortAmmon My understanding is that FP is about reducing state to increase parallelism and reduce complexity. Cryptographic algos are designed to be difficult to parallelize and the state is often an integral part of the design. So using FP would a square peg...
    – Aron
    Mar 9, 2022 at 18:56
  • 2
    @Aron True, using FP to solve that problem is probably an antipattern. But writing an FP program that invokes a C function to do some crypto is pretty common, and I think that's what Cort was suggesting in their last sentence. Mar 9, 2022 at 20:05
  • 1
    @CortAmmon well, that's perhaps true if you count also the truely trivial things that can be done in any modern language with some kind of range-based for loop / implicit vectorization etc.. But anybody who nowadays still uses indices for that kind of task deserves to be slapped about the head with a physical printout of their code. The "0.5%" of code that don't easily translate to recursive-Haskell-on-lists still include lots of stuff that's pretty straightforward with arrays, like updating a cell in a multidimensional array based on all its neighbours. No contrived crypto examples needed. Mar 10, 2022 at 17:08
25

This is not an index-heavy operation, in fact you can do this with a one-liner with scanl1 :: (a -> a -> a) -> [a] -> [a]:

prefixList = scanl1 (+)

indeed, for the list of Nums, we get:

Prelude> prefixList [1 .. 9]
[1,3,6,10,15,21,28,36,45]

scanl1 takes the first item of the original list as initial value for the accumulator, and yields that. Then each time it takes the accumulator and the next item of the given list, and sums these up as new accumulator, and yields the new accumulator value.

Often one does not need indexing, but enumerating over the list is sufficient. Imperative programming languages often work with for loops with indexes, but in many cases these can be replaced by foreach loops that thus do not take the index into account. In Haskell this also often helps to make algorithms more lazy.

If you really need random access lookups, you can work with data structures such as defined in the array and vector packages.

14

This isn't a Haskell answer, but you tagged the question lisp so here's an answer in Racket: this is both entirely functional and shows that you don't need indices for this problem.

What this function does is take a stream of numbers and return the prefix stream for it. This is all done lazily.

(define (prefix-stream s)
  (let ps-loop ([st s]
                [p 0])
    (if (stream-empty? st)
        empty-stream
        (let ([np (+ p (stream-first st))])
          (stream-cons 
              np 
              (ps-loop 
                  (stream-rest st)
                  np))))))

So now

> (stream->list (prefix-stream (in-range 1 10)))
'(1 3 6 10 15 21 28 36 45)

But of course you can also do this:

> (prefix-stream (in-naturals))
#<stream>

That's obviously not a stream you can convert to a list, but you can look at parts of it:

(stream->list (stream-take (prefix-stream (in-naturals)) 10))
'(0 1 3 6 10 15 21 28 36 45)
> (stream->list (stream-take (stream-tail (prefix-stream (in-naturals)) 1000) 10))
'(500500 501501 502503 503506 504510 505515 506521 507528 508536 509545)

(Note that in-naturals considers the naturals to start from 0, as is right and proper.)

6

In Clojure this could be written as:

(defn prefix-list [nums]
  (loop [i 1
         prefix nums]
    (if (= i (count nums))
      prefix
      (recur (inc i) (assoc prefix i (+ (get prefix i) (get prefix (dec i))))))))

(prefix-list [1 2 3 4 5 6 7 8 9]) returns [1 3 6 10 15 21 28 36 45]

In Clojure, data is generally immutable (it can't be modified). The function assoc in this case takes a vector, and returns a new vector like the original, but with the ith element changed. This may sound inefficient, but the underlying data structures allow the update to be done in near constant time (O(log32(n))).

As others have pointed out, this particular problem could be coded without using indexed vectors, but I'm endeavoring to provide a solution that's true to your original Java code in the use of an indexed array.

5

I know you asked about functional languages, but I just wanted chime in uninvited to mention that Python, being a multi-paradigm language, also has this as the nice higher-order itertools.accumulate function.

Accumulate takes a collection and returns an iterator of its partial sums, or any custom binary function. The functional Python code equivalent to your example would be just:

from itertools import accumulate
print(list(accumulate(range(1, 10))))

In general, the Python itertools and functools standard library modules offer excellent tooling for functional programming.

1
3

Others have pointed out that your particular example can be handled nicely with functions like scanl, so lets look at the broader question of "index-heavy operations which rely strongly on loops/order-of-execution". We can break down the issue into three concerns:

  1. Indexing
  2. Looping
  3. Mutation

Indexing into a data structure is supported wherever the concept of indexing makes sense. For example, List and Vector both support indexing. As others have pointed out, Vector has better performance if your index is random but that is surprisingly rare.

Imperative loops can be replaced directly with recursive functions (see Wikipedia) although there are so many "higher-order functions" (functions that take functions as arguments) implemented in Prelude and standard libraries that you will need explicit recursion rarely. scanl is an example of this. It allows you to avoid an explicit recursive call by farming it out to a prewritten function. That function, however, is defined recursively. The compiler may be optimizing away that recursion into a loop when it generates machine code.

Finally, you might have an array of numbers and really, really want to mutate the values in the array over a series of steps. Everyone in this thread, including me, would try very hard to talk you out of this and get you to think in a more "functional" way. But if we fail then you can use the state thread monad. This gives you a way to mutate your data structures locally (scary) within a function while interacting with things outside the function only with immutable (not scary) data structures and hence ensures that the function is referentially transparent.

1

This functionality is also called a "cumulative sum", and another Python method is to use numpy (which, being written in C, is ultra fast):

nums = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9]) # or np.arange(1, 10) or np.arange(9)+1
print(nums.cumsum())

Output:

[1, 3, 6, 10, 15, 21, 28, 36, 45]
0

There are built-in functions in Elixir that is similar to Haskell's: Enum.scan/2 and Enum.scan/3:

Enum.scan(1..9, 0, fn element, acc -> element + acc end) |> IO.inspect()
# yields:
# [1, 3, 6, 10, 15, 21, 28, 36, 45]

When you first switch from OO to functional ways of thinking, the indexes can be difficult to let go of, but I've found that nearly every problem where I would have formerly reached for an indexed solution (e.g. a for next loop) has an elegant counterpart in a map or reduce function, or in some form of tail recursion.

For example, you could build your own function(s) to handle this operation by using tail-recursion and a manual accumulator:

defmodule Foo do
  def bar(nums, acc \\ [])

  # We've reached the end of input: return the accumulator (reversed)
  def bar([], acc), do: Enum.reverse(acc)

  # The very first call is special because we do not have a previous value
  def bar([x | tail], []) do
    bar(tail, [x])
  end

  # All other calls land here
  def bar([x | tail], [prev | _] = acc) do
    bar(tail, [x + prev | acc])
  end
end


nums =   [1, 2, 3, 4,  5,  6,  7,  8,  9]
prefix = Foo.bar(nums)
IO.inspect(prefix)

# Yields the same result:
# [1, 3, 6, 10, 15, 21, 28, 36, 45]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.