Arc Forumnew | comments | leaders | submitlogin
3 points by kens 6150 days ago | link | parent

Is ac-niltree/ac-denil a constant overhead, or does it make some O(1) operations into O(n) operations? Hopefully the nil/denil traverses the whole list only when you're already traversing the whole list. But I haven't been able to convince myself that's always the case. This is on my list of things to investigate, but has anyone already figured this out?


1 point by eds 6149 days ago | link

I'm not completely sure, but I think this is a compile-time overhead. So when you type directly into the toplevel, its a O(n) overhead, but when you execute a function defined in arc, executing the function itself should be less additional overhead because it was compiled to a scheme function in the original def.

  ; translate fn directly into a lambda if it has ordinary
  ; parameters, otherwise use a rest parameter and parse it.
  (define (ac-fn args body env)
    ; ...

-----