CODEWITHSUNDEEP
f#functional-programming
Tomb_Raider_Legend
Tomb_Raider_Legend

Reputation: 451

Array pattern matching

Is it possible to iterate through an array using pattering matching just like we do with lists in F#? I tried something like this:

type Alphabet = A | B

let rec calc (l: Alphabet []) = match l with
                               |l when l.[0] = A -> 5+(calc l.[1..])
                               |l when l.[0] = B -> 10+(calc l.[1..])
                               |l when l = [||] -> 0
calc [|A;A;B|]

The problem seems to be that the loop goes on and results a stackoverflow. Is it possible to do so?

Upvotes: 3

Views: 1516

Answers (1)

Vandroiy
Vandroiy

Reputation: 6223

I think you are trying to do this:

let toInteger = function
    | A -> 5
    | B -> 10

[|A; A; B|] |> Array.sumBy toInteger

In pattern matching, you can use an array pattern: for example, [|a; b; c|] matches against a three-element array. But there is no :: operator for arrays, so it's cumbersome to use an array the way you'd use a list. This is because you can't get the array's tail as a new array without copying it.

There are a number of issues with the question's code:

  • It crashes due to going out of bounds of the array. This is because you are not verifying that the .[1..] slice exists.
  • It is not tail recursive. This may be the reason you're seeing a stack overflow on long lists.
  • Two features are mixed into one function, making it complicated to read: the conversion to integer and the summation.
  • The compiler cannot verify that the pattern match covers all cases, so it issues a warning.
  • As hinted before, the copying of arrays is costly. This algorithm has O(n^2) in the length of the array, making it extremely expensive for long arrays. Unlike Array.sumBy or a tail-recursive function indexing into the array, which don't have to copy the array at all.

The heart of the issue here is the difference between arrays and singly linked immutable lists. Arrays are suited for iterating over them by increasing an index (which Array.sumBy does internally), while lists allow to treat their tail as an independent list without any copying (which List.sumBy does internally). It's usually best to use each data structure the way it is intended to be used.

Upvotes: 8

Related Questions