Hacker News Reader

Comment by loup-vaillant | Hacker News Reader

Something 's not right. Still too complex. Ah. Lists are recursive. Their treatment should be recursive as well. Let's see…

  void remove_if(node ** head, remove_fn rm)
  {
      node * entry = *head;
      if (rm(entry))
      {
          *head = entry->next;
          free(entry);
      }
      else
          head = &entry->next;
      remove_if(head, rm);
   }

Ahh, much better: Now we can refactor:

  void remove_head(node ** head)
  {
      node * entry = *head;
      *head = entry->next;
      free(entry);
  }

  void remove_if(node ** head, remove_fn rm)
  {
      if (rm(*head))
          remove_head(head)
      else
          head = &entry->next;
      remove_if(head, rm);
   }

I'm sure GCC will be able to optimize away the tail call.

Edit: oops, I forgot to test for empty lists, which was implicit in the for loop I set out to remove…

View on HN

Tail calls are considered very bad style, for good reason. gcc can indeed optimize them away, at a sufficiently high level of optimization; but it's not very nice to write code that, e.g., runs out of stack space only when compiled for debugging.

"...very bad style"? That's quite an overstatement. You can enable individual optimizations with gcc. Just add `-foptimize-sibling-calls` to the debug CFLAGS and you're set. Tada! Straightforward code and debug-ability.

But that would be making your code dependent on a particular feature of a particular compiler. If you then want to port your code to Windows (lots of open-source code runs there too), you'll have to deal with the problem again there. If you wrote the code with an explicit loop, it would just work everywhere.

On the other hand, for a linked list, recursion follows immediately from the definition of the list, while iteration does not. I would rather have my debugger allocate a large stack or compile the code so that TCO was enabled even when I was debugging than have to deal with implementations that do not clearly follow from a high-level design.

Lists are recursive, right. Better than double pointer indirection is to have the function return the new head. Note that the following code is not functional, but returning the new head makes it cleaner.

    node *remove_if(node *head, remove_fn rm)
    {
        if (rm(head)) {
            return remove_if(head->next);
        }
        head->next = remove_if(head->next);
        return head;
     }

A good use of this technique (returning pointers to the resulting node) is the following code which very cleanly implements AVL trees in C (from http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-... -- scroll to the end (sorry, main article in Romanian)):

    #define max(a, b) ((a) > (b) ? (a) : (b))
    #define geth(n) (n->h = 1 + max(n->l->h, n->r->h))
     
    struct node
    {
          int key, h;
          struct node *l, *r;
    } *R, *NIL;
    typedef struct node node;
     
    void init(void)
    {
          R = NIL = (node *) malloc(sizeof(node));
          NIL->key = NIL->h = 0,
                  NIL->l = NIL->r = NULL;
    }
     
    node* rotleft(node *n)
    {
          node *t = n->l;
     
          n->l = t->r, t->r = n,
                  geth(n), geth(t);
          return t;
    }
     
    node* rotright(node *n)
    {
          node *t = n->r;
      
          n->r = t->l, t->l = n,
                  geth(n), geth(t);
          return t;
    }
     
    node* balance(node *n)
    {
          geth(n);
          if (n->l->h > n->r->h + 1)
          {
                  if (n->l->r->h > n->l->l->h)
                          n->l = rotright(n->l);
                  n = rotleft(n);
          }
          else
                  if (n->r->h > n->l->h + 1)
                  {
                          if (n->r->l->h > n->r->r->h)
                                  n->r = rotleft(n->r);
                          n = rotright(n);
                  }
          return n;
    }
     
    node* insert(node *n, int key)
    {
          if (n == NIL)
          {
                  n = (node *) malloc(sizeof(node));
                  n->key = key, n->h = 1, n->l = n->r = NIL;
                  return n;
          }
          if (key < n->key)
                  n->l = insert(n->l, key);
          else
                  n->r = insert(n->r, key);
          return balance(n);
    }
     
    node* erase(node *n, int key)
    {
          node *t;
          if (n == NIL) return n;
          if (n->key == key)
          {
                  if (n->l == NIL || n->r == NIL)
                  {
                          t = n->l == NIL ? n->r : n->l;
                          free(n); return t;
                  }
                  else
                  {
                          for (t = n->r; t->l != NIL; t = t->l);
                          n->key = t->key,
                                  n->r = erase(n->r, t->key);
                          return balance(n);
                  }
          }
          if (key < n->key)
                  n->l = erase(n->l, key);
          else
                  n->r = erase(n->r, key);
          return balance(n);
    }
     
    int search(node *n, int key)
    {
          if (n == NIL) return 0;
          if (n->key == key) return 1;
          if (key < n->key)
                  return search(n->l, key);
          else
                  return search(n->r, key);
    }

Reply on news.ycombinator.com