3

I have the following code for getting the length of a list in prolog, it works recursively. Is there any other way for getting the length?

len([], 0).
len([H|T], N) :-
    len(T, NT), N is NT + 1.

Any suggestions would be appreciated.

false
  • 10,264
  • 13
  • 101
  • 209
  • 5
    You can use the built-in predicate, `length(List, N)`. :) Why do you need it to be non-recursive? – lurker Dec 30 '14 at 17:20
  • 2
    I am learning prolog and I am wonder is there other ways than recursion for doing simple things in prolog.Does the built-in predicate itself use recursion again? –  Dec 30 '14 at 17:25
  • 5
    Whether the built-in uses recursion in Prolog or some other language is dependent upon the Prolog implementation. There are ways to manipulate lists without recursion, but it usually involves other predicates like `append`, `maplist`, or `length`, for example. And these may or may not be written recursively inside of a given Prolog implementation. Recursion is otherwise essential to iterate through all the elements of a list. If you just want the first element, you can do things like `[H|T] = List` to grab the head (first) element, `H`, or the tail list, `T`. – lurker Dec 30 '14 at 17:29

3 Answers3

4

You are asking the wrong question :)

But seriously: the only sensible way of finding the length of a list is to use the built-in length/2. How it is implemented is irrelevant -- more important are its semantics:

?- length([a,b], 2).
true.

?- length([a,b], 4).
false.

?- length([a,b,c], Len).
Len = 3.

?- length(List, 3).
List = [_G937, _G940, _G943].

?- length(List, Len).
List = [],
Len = 0 ;
List = [_G949],
Len = 1 ;
List = [_G949, _G952],
Len = 2 . % and so on

Either way, it doesn't get simpler than that. Any other way of finding the length of a list, or checking for the length of a list, or creating a list of a certain length, or enumerating lists of increasing length is going to be less "simple" than using length/2.

And then: learning Prolog means learning how length/2, and the other nicely declarative built-ins can be used.

Repeating an element N times

Splitting a list into segments of some length

Exactly one pair in a list

Rotate a list

I am sure you can think of many other uses of length/2.

Community
  • 1
  • 1
  • 7
    `length/2` in many implementations uses [Brent's algorithm](http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm) to determine length and detect cycles - which is verily of unsurpassed cleverness. – false Dec 30 '14 at 21:54
2

Here is an iterative solution that uses repeat/0 predicate:

getlength(L,N) :-
    retractall(getlength_res(_)),
    assert(getlength_res(0)),
    retractall(getlength_list(_)),
    assert(getlength_list(L)),
    repeat,
        (
            getlength_list([]), !, getlength_res(N)
        ;
            retract(getlength_res(V)), W is V + 1, assert(getlength_res(W)),
            retract(getlength_list([_|T])), assert(getlength_list(T)), fail
        ).

This solution creates and retracts facts getlength_res/1 and getlength_list/1 as it walks through the list, replacing the old list with a shorter one, and the old number with a number that is greater by one at each iteration of repeat/0. In a sense, the two dynamically asserted/retracted facts behave very much like assignable variables of imperative languages.

Demo.

In general, iterative solutions in Prolog are harder to read than their recursive counterparts. This should come as no surprise, considering that anything that has an effect of an assignment statement of an imperative programming language goes against the grain with Prolog's design philosophy.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 1
    I wasn't thinking about the `assert` approach (+1). It's not only harder to read, but very inefficient in this case, and not really a recommended alternative. :) – lurker Dec 30 '14 at 17:55
  • 2
    @lurker It goes without saying that I would strongly recommend against these kinds of solutions, because one gets zero advantages, slower execution speeds, and the statement count that is up 7 (yes, seven) times. Thanks for the comment! – Sergey Kalinichenko Dec 30 '14 at 18:06
  • 1
    Indeed. I just wanted to underscore the issue, as I wasn't sure of the OP's experience level with Prolog. There are many perhaps less obvious scenarios where list processing is preferred over use of `assert` and `retract`. I do like the answer, though, as it illustrates this aspect of Prolog. – lurker Dec 30 '14 at 18:12
  • No, that's only playing more on words. – false Dec 30 '14 at 21:52
0

Sorry I could not resist to try out this "challenge":

Input=[a,b,b,b,b,b,b,b,b,a,b,c,d,f], between(1,inf,K),findall( _,between(1,K,_),FreeList), ( FreeList=Input,!,true).

findall/3 is doing the behind-the-scenes recursion, code is making unifications of lists FreeList and Input until they unify

re Paul
  • 122
  • 1
  • 8