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.

score 2 · Accepted Answer · edited May 23 '17 at 12:15

2

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), ...

edited May 23 '17 at 12:15

Community

1
1

answered Jan 20 '15 at 23:37

false

10,264
13
101
209

1

That worked like a charm. My full expresion: gencnts(I,LevelCounts) :-findall(T-Y,(ancecnt(I,Y,0,T,13)),F), sort(F,L),group_pairs_by_key(L,M), list_bylength(M,LevelCounts). It summarized 7 generations of ancestry to: [1-7, 2-43, 3-56, 4-87, 5-110, 6-80, 7-15] – softbrass Jan 21 '15 at 01:40

score 0 · Answer 2 · answered Jan 22 '15 at 14:57

0

a lot of list processing can be performed by findall/3, using member/2 as 'cursor'.

list_bylength(KLs, KNs) :-
  findall(K-L, (member(K-Ls,KLs),length(Ls,L)), KNs).

answered Jan 22 '15 at 14:57

CapelliC

59,646
5
47
90

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

2 Answers2