Hacker News Reader

Comment by Zak | Hacker News Reader

Write code that returns the length of a string without using any built-in functions.

It took me a while to realize that they're probably not counting infix operators that behave like functions except for the syntax. Accomplishing this task in Lisp or Haskell would be nearly impossible.

View on HN

Doesn't seem all that tough to me

  my_len_acc :: [a] -> Int -> Int
  my_len_acc [] so_far = so_far
  my_len_acc (_:xs) so_far = my_len_acc xs $ so_far + 1
   
  my_len :: [a] -> Int
  my_len some_str = my_len_acc some_str 0

$ and + are built-in functions being used with infix syntax.

Without such built-in functions like application or arithmetic this is impossible in every language.

Consider: without application you cannot consider such a language general recursive and therefore it is not Turing complete according to the Church-Turing thesis.

Hence my claim about the near-impossibility of the task.

That's disingenuous. When they say "no built-in functions", they really only mean "don't use a library function that makes this task trivial." Which eliminates 'strlen' in C, 'length' in Haskell, 'len' in Python, etc.

sort of trivial in python with just statements: i=0 for x in thestring i+=1 print i

  (defun strlen (str)
    (loop for i from 0
          for char across str
          finally (return i)))

Works in my emacs... I (require 'cl).

I suppose everything you called is a special form. It should have occurred to me that the loop macro could do it. Is the Loop macro Turing complete?

Then don't write it in Lisp or Haskell. If they don't specify a language, use one that makes sense.

Reply on news.ycombinator.com