Prolog - Finding object with shortest inner List in a List

Question

I have a large list BIGLIST that consists solely of any number of smaller lists SMALLLIST, which themselves contain another list INNERLIST in their first index. I need to design a predicate that can find the SMALLLIST with the shortest INNERLIST. No INNERLIST has a length greater than 9. For example:

BIGLIST = [
          [[1,2,3],3824],
          [[4,5],89],
          [[6],283],
          [[2],14],
          ]

The SMALLLIST with the shortest INNERLIST here is [[6],283], despite the existence of [[2],14] (they are the same length). I've written a predicate shortest/2 like the following, but the desired SMALLLIST never gets bound to Shortest:

shortest(BIGLIST,Shortest) :-
    Num = 10,
    get_shortest(BIGLIST,Shortest,Num).

get_shortest([],_,_).                                 %list is empty, stop
get_shortest([SMALLLIST|Tail],Shortest,ShortLen) :-   %better SMALLLIST found
    nth0(0,SMALLLIST,INNERLIST),                           %get INNERLIST
    length(INNERLIST,Len),
    Len < ShortLen,
    NShortest = SMALLLIST,
    NShortLen = Len,
    get_shortest(Tail,NShortest,NShortLen),
    Shortest = NShortest.
get_shortest([_|T],Shortest,ShortLen) :-             %skip head if it is not a better value
    get_shortest(T,Shortest,ShortLen).

Thanks for the help.

You could do something like, setof( N-[L|T], (member([L|T], BIGLIST), length(L, N)), S ), S = [_-SMALLIST|_]. but it will pick the last of the shortest if there's a "tie", rather than the first. — lurker
Head should be SMALLLIST, but there are other flaws in your code. Have you considered using ->? And if you just want the head, use [INNERLIST|_]=SMALLLIST. — Patrick J. S.

mat mat · Accepted Answer · 2014-10-01T18:19:08

In such cases keysort/2 comes in handy. For example:

biglist_smallest(Bs, E) :-
        maplist(element_with_length, Bs, LEs),
        keysort(LEs, [_-E|_]).

element_with_length(Elem, L-Elem) :-
        Elem = [Inner|_],
        length(Inner, L).

With your data:

biglist([[[1,2,3],3824],
         [[4,5],89],
         [[6],283],
         [[2],14]
         ]).

we get:

?- biglist(Ls), biglist_smallest(Ls, E).
Ls = [[[1, 2, 3], 3824], [[4, 5], 89], [[6], 283], [[2], 14]],
E = [[6], 283].

Prolog - Finding object with shortest inner List in a List

2 Answers