How do I "reduce" a Prolog list of pairs?

Question

I'm trying to do some graph analysis using PROLOG. In particular I want a list of pairs which indicate the number of nodes at each deeper level from the root. I'm able to produce a list of pairs of the form:

M = [1-[431, 441, 443, 444, 445, 447, 449], 2-[3, 5, 7, 8, 409, 451|...]].

The pair key is the graph level; the pair value is the list of nodes at that level; whereas I want the pair value to be a count of the nodes. But I can't figure out to reduce M to N.

N = [1-7],[2,20,],...........[8-398]

where N indicates 7 nodes at the 1th level etc.... perhaps I need a good set of examples working with pairs. Simpler data could be M=[1-[a,b,c],],2-[d,e]] should reduce to N=[1-3,2-2] Any pointers would be much appreciated.

false false · Accepted Answer · 2015-01-20T23:37:04

You want to map a list of such pairs to another list element-wise as follows

list_bylength(KLs, KNs) :-
   maplist(el_len, KLs, KNs).

el_len(I-L,I-N) :-
   length(L, N).

Alternatively:

list_bylength2([], []).
list_bylength2([I-L|ILs], [I-N|INs]) :-
   length(L, N),
   list_bylength2(ILs, INs).

And most compactly, using library(lambda):

..., maplist(\ (I-L)^(I-N)^length(L,N), ILs, INs), ...

How do I "reduce" a Prolog list of pairs?

2 Answers