在 C 中连接，就像 Haskell 中的列表

Question

我最终写了一个从 Haskell 到 C 的翻译器，这是一种业余爱好..

Haskell 的 (:) 函数，类型为 a -> [a] -> [a] 是我想在 C 中做的。

1 : [2,3] 实际上是 1 : (2 : (3 : [])) 如果我没记错的话。

假设我想创建一个无限列表，其中的数字越来越多:

lst i = i : lst (i + 1)

我如何在 C 中执行此操作？我想象最终产品看起来像这样:

int* lst(int i) {
    return cons(i, lst(i + 1));
}

到目前为止我的想法:

• C 有数组。
• 数组需要定义长度，这与递归推理冲突。
• C 有指针。
  • 数组在作为参数传递时会退化为指针，因此，不妨使用纯指针。
  • array[i] 等同于 *(ptr + i)，我想我可以用它来解决必须定义事物的问题不知道(列表的最终长度等)。

不过我不确定 cons 的实现。我最好的猜测是:

int* cons(int head, int *tail) {
    int *ptr;
    *(ptr + 1) = *tail;
    *ptr = head;
    return ptr;
}

指针对我来说很难，取消引用等等，我不太了解 C，我的大脑很痛。我只想制作一个包含头部和尾部的指针。目前顺序并不重要。

它可以编译，但仅此而已。帮助将不胜感激，我愿意接受建议，我什至不确定我是否走在正确的轨道上，或者是否有可能。

Answer 1

首先，这是您的函数正在执行的操作:

int* cons(int head, int *tail) {
    int *ptr; // Declare a pointer on the stack
    *(ptr + 1) = *tail; // Set the int located after the one pointed by the (uninitialised) pointer ptr to the value pointed to by tail
    *ptr = head; // Set the value that the (still unitiliased) points to to head
    return ptr; // Return an uninitialised value
}

其次，你要的是一个链表。您可以创建一个结构，就像 data List a = [] | (:) a (List a) in C. 例如，

typedef struct list {
  void *element;
  struct list *next;
} list_t;

现在 cons 看起来像这样:

list_t *harp_cons(void *element, list_t *rest) {
  list_t *list  = (list_t*)malloc(sizeof(struct list_t));
  list->element = element;
  list->next    = rest;
  return list;
}

这是在堆上分配数据，所以之后需要释放它。您可以提供如下所示的函数 free_list。 (假设为了简单起见，可以使用 free() 简单地释放元素。)

void free_list(list_t *list) {
  if(list != NULL) {
    if(list->next != NULL) {
      free_list(list->next);
    }
    free(list->element);
    free(list);
  }
}

我只是从我的一些开源代码中提取了该代码。

如果您想查看(某种)列表 API 的完整实现:​​https://github.com/thoferon/harp/blob/master/libharp/list.c .