suguni (1) [Avatar] Offline
#1
def reverse: AList = {
if (isEmpty) Empty
else head :: tail.reverse
}

do not reverse list, and is linear.

def reverse:AList = if (isEmpty) Empty else tail.reverse.append(head)

is a correct reverse function, and sqr(n) time.
PedroPS (12) [Avatar] Offline
#2
Re: p105. no tail recursion reverse function
Sorry if I'm wrong (I'm not proficient on FP), but... Would your solution create an AList with an "Empty" object as a head of the result "reversed" list?

In the afirmative case. Is that correct? Shouldn't it be another "Empty" object as a "last" node?