Implement F# List.scan in C?

Admin 1
Viewed 162

How would you implement a function with the same behavior as List.scan in F#?

Here is the description:

Applies a function to each element of the collection, threading an accumulator argument through the computation. This function takes the second argument, and applies the function to it and the first element of the list. Then, it passes this result into the function along with the second element, and so on. Finally, it returns the list of intermediate results and the final result. (link)

Of course I have attempted myself and here is my pseudocode (I do not expect you to provide working c-code btw): For the call scan(myop, ne, x), I have the pseudocode

int n = length(x);
char *b = (char*)malloc(n); //Allocate n bytes
b[0] = ne;
int i = 0;
while (i < n) {
    bool tmp = myop(b[i-1], x[i]);
    bool b[i] = tmp;
    i = i+1;
}
bool list y = b;

but this fails for i > 0 since then b[i] is not initialized. How would you implement this?

f# c
2 Answers

but this fails for i > 0 since then b[i] is not initialized

In your pseudo code:

bool tmp = myop(b[i-1], x[i]);

It will be failed when i = 0 (it means at the first time you enter the while loop), because you try to access the index -1 (i = 0, so b[i-1] becomes b[-1]) of b, it is undefined behavior.

You have to begin the while loop at i = 1 at least. So, before the loop:

b[0] = ne;
int i = 0;

Can change to:

b[0] = ne;
// do something with b[0] if you want.
int i = 1;
user_82057660

In your code, you refer to the previous element even for i == 0, which is incorrect. You could special case the first element by storing b[0] = myop(ne, x[0]) and start the loop at i = 1, but this solution would not work for an empty source list (n == 0). Furthermore, length(x) cannot be computed from a pointer, only from an actual array as sizeof(x) / sizeof(*x). It is best to pass the size as a separate argument.

Here is a C function that performs the semantics of List.scan for int arguments, taking a pointer to the function, an initial value, an array of int values, the length of this array and a pointer to the destination array, which can be the same as the source array:

int array_scan(int (*func)(int, int), int v1, const int *src, size_t count, int *dest) {
    for (size_t i = 0; i < count; i++) {
        int v2 = src[i];
        dest[i] = v1;
        v1 = func(v1, v2);
    }
    return v0;
}

In C there is no way to define lambda expressions inline, so you must define the function separately with a name and pass it explicitly to array_scan.

user_45932670
Related