without type_check

type string(object o) if sequence(o) then
    if not length(o) then return 1 end if
    for i = 1 to length(o) do
	if not integer(o[i])          then return 0 end if
	if o[i] != and_bits(o[i],#FF) then return 0 end if
    end for
return 1 end if return 0 end type

constant STRING = 1, NUMBER = 2

type element(object o) if sequence(o) and
    length(o) = 2 and
    string(o[1]) and
    integer(o[2])
then
return 1 end if return 0 end type

type list(object o) if sequence(o) then
    if not length(o) then return 1 end if
    for i = 1 to length(o) do
	if not element(o[i]) then return 0 end if
    end for
return 1 end if return 0 end type

function bfind(string s, list L)
    -- returns n > 0 if found at that position
    -- returns n = 0 if list is empty
    -- returns n < 0 if -n is the position the element
    --                 _would_ be at if it were present

    integer c, lo, hi, mid
    hi = length(L)
    if not hi then return 0 end if
    lo = 1
    mid = 1
    c = 0
    while lo <= hi do
	mid = floor((lo+hi)/2)
	c = compare(s, L[mid][STRING])
	if c = 0 then
	    return mid
	elsif c < 0 then
	    hi = mid - 1
	else -- c > 0
	    lo = mid + 1
	end if
	--if get_key() != -1 then exit end if
    end while
    return (c<0)-mid
end function

function listinsert(string s, list L)
    integer pos, len
    pos = bfind(s, L)
    if pos > 0 then
	-- ignore - already in list
	printf(2,
	    "DEBUG: Element %s already exists at position %d with tag %d.\n",
	    {L[pos][STRING], pos, L[pos][NUMBER]}
	)
	return L
    end if
    -- pos <= 0
    pos *= -1
    len = length(L)
    return L[1..pos] & {{s,len}} & L[pos+1..len]
end function

procedure listprint(list L)
    integer len
    len = length(L)
    if not len then puts(1, "{}\n") return end if
    puts(1, "{\n")
    for i = 1 to len do
	printf(1, "  {%-15s, %d}", {"\"" & L[i][STRING] & "\"", L[i][NUMBER]})
	if i != len then puts(1, ",") end if
	puts(1, "\n")
    end for
    puts(1, "}\n")
end procedure

atom T
list mylist
mylist = {}

T = time()

for i = 1 to 4000 do
    mylist = listinsert('@'+rand(repeat(26, rand(6)+2)), mylist)
end for

? time() - T