How do purely functional languages handle index-based algorithms?-CodePudding

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.

CodePudding user response：

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".

CodePudding user response：

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.