将Haskell行转换为C.

这段代码到C的翻译是什么,更确切地说'foldl'的作用是什么？

我认为这段代码可能是Haskell,但我不太确定.

foldl (\x y -> y:x) [] [1..42]

bheklilr.. 9

将这条短线转换为C将是一项相当大的工作,因为它需要定义链表并使用指针.相反,我只想尝试解释foldl.

将foldl在Haskell函数的类型foldl :: (a -> b -> a) -> a -> [b] -> a.这里是a和b类型变量,可以是任何类型,只要你是一致的.让我们专注于您正在处理的问题.首先,我们看到传递给的列表foldl是[1..42]有类型的[Int].这适合foldl作为[b]参数,所以因为[b] ~ [Int](~是类型相等符号),我们可以推导出它b ~ Int.传递给的第二个值foldl是[],在这种情况下将具有类型[Int],所以a ~ [Int].如果我们将这些插回到我们得到的完整类型签名中

foldl :: ([Int] -> Int -> [Int]) -> [Int] -> [Int] -> [Int]

那么lambda函数(\x y -> y : x)呢？它所做的就是获取一个列表,一个元素,并将该元素添加到列表的前面.一个例子是

> let f = (\x y -> y : x)
> f [1, 2, 3] 0
[0, 1, 2, 3]
> f [] 1
[1]
> f (f [1, 2] 3) 4
[4, 3, 1, 2]

什么foldl与该函数的作用是反复调用它,喂养它从列表中值.在[]作为第二个参数是初始值.所以在一个简短的清单上,它看起来像

foldl (\x y -> y : x) [] [1, 2, 3, 4]
  (\x y -> y : x) [] 1 = 1 : [] = [1]
foldl (\x y -> y : x) [1] [2, 3, 4]
  (\x y -> y : x) [1] 2 = 2 : [1] = [2, 1]
foldl (\x y -> y : x) [2, 1] [3, 4]
  (\x y -> y : x) [2, 1] 3 = 3 : [2, 1] = [3, 2, 1]
foldl (\x y -> y : x) [3, 2, 1] [4]
  (\x y -> y : x) [3, 2, 1] 4 = 4 : [3, 2, 1] = [4, 3, 2, 1]
foldl (\x y -> y : x) [4, 3, 2, 1] [] = [4, 3, 2, 1]

所以这个特定的折叠反转了一个列表.

C中的一个实现只专门用于int链接列表(没有多态),没有懒惰,没有不变性

#include 
#include 

struct Node_
{
    int val;
    struct Node_ *next;
};

typedef struct Node_ Node;
typedef struct Node_ * NodePtr;

NodePtr mkNode(int val) {
    NodePtr n = (NodePtr) malloc(sizeof(Node));
    n->val = val;
    n->next = NULL;
    return n;
}

NodePtr reverse(NodePtr head) {
    NodePtr current = head;
    NodePtr newHead = mkNode(head->val);

    NodePtr temp;
    while (current->next != NULL) {
        temp = mkNode(current->next->val);
        current = current->next;
        temp->next = newHead;
        newHead = temp;
    }

    return newHead;
}


NodePtr fromTo(int start, int stop) {
    NodePtr root = mkNode(start);
    NodePtr conductor = root;
    NodePtr temp;
    while (++start <= stop) {
        temp = mkNode(start);
        conductor->next = temp;
        conductor = conductor->next;
    }
    return root;
}

void printNode(NodePtr root) {
    NodePtr copy = root;
    while (copy->next != NULL) {
        printf("%d ", copy->val);
        copy = copy->next;
    }
    printf("%d\n", copy->val);
}

int main(int argc, char const *argv[])
{
    NodePtr numbers = fromTo(1, 10);
    printNode(numbers);
    printNode(reverse(numbers));
    return 0;
}

NodePtr foldl_NodePtr(NodePtr (*func)(NodePtr, int), NodePtr initial, NodePtr root) {
    NodePtr val = initial;
    NodePtr copy = root;
    while (copy->next != NULL) {
        val = func(val, copy->val);
        copy = copy->next;
    }
    val = func(val, copy->val);
    return val;
}

NodePtr lambda(NodePtr node, int val) {
    NodePtr temp = mkNode(val);
    temp->next = node;
    return temp;
}

NodePtr reverse_foldl(NodePtr root) {
    NodePtr temp = mkNode(root->val);
    return foldl_NodePtr(lambda, temp, root->next);
}

int foldl_int(int (*func)(int, int), int initial, NodePtr root) {
    int val = initial;
    NodePtr copy = root;
    while (copy->next != NULL) {
        val = func(val, copy->val);
        copy = copy->next;
    }
    val = func(val, copy->val);
    return val;
}

int add(int x, int y) { return x + y; }

int sum(NodePtr root) { return foldl_int(add, 0, root); }