0

Need to know what are these L1, [H1 | L2]. No idea at all.

bubSort([],[]) :- !.
bubSort([H],[H]) :- !.
bubSort(L,SL) :- append(L1, [H1,H2|L2], L), H2 < H1, append(L1, [H2,H1|L2], NL), !,
                 bubSort(NL,SL).
bubSort(L,L).

This compiles and sorts the list well. But I need to understand this mechanism. Specially the how this append works.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Indrajith
  • 11
  • 2
  • 1
    Explanation about what? The bubble sort algorithm? It is well explained elsewhere. `append` predicate? It is in the documentation of SWI Prolog. – Eugene Sh. Aug 14 '17 at 13:04
  • `append(A, B, C)` means `B` appended to `A` is `C`. Or equivalently, `A` concatenated with `B` is `C`. – lurker Aug 14 '17 at 14:14
  • Need to know what are these L1, [H1 | L2]. No idea at all – Indrajith Aug 14 '17 at 15:47
  • You need to go learn some very fundamental Prolog evidently. Book or tutorial. `L1` is just a variable. Used in `append`, it represents a list since `append` operates on lists. `[H1|L2]` is a Prolog list with head `H1` and tail `L2`. – lurker Aug 14 '17 at 19:32
  • was my answer helpful? do you have any more questions or concerns? – Will Ness Aug 28 '17 at 12:07

1 Answers1

1
  • L1 : a logical variable (the name suggestive of a "list")
  • L1 = [H1 | L2] : the list L1 has H1 as its head element, and L2 is a list of all the rest of its elements
  • append(L1, [H1,H2|L2], L) : the list L consists of the elements of a list L1, then the element H1, then the element H2, and the elements of the list L2 after that
  • H2 < H1 : an arithmetical value referred to by the logical variable H2 is smaller in magnitude than the arithmetical value referred to by the logical variable H1
  • append(L1, [H2,H1|L2], NL) : the list NL consists of the elements of a list L1, then the element H2, then the element H1, and the elements of the list L2 after that
  • bubSort([],[]) :- !. bubSort of an empty list [] is an empty list, []
  • bubSort([H],[H]) :- !. bubSort of a singleton list [H] (a list with just one element, H, in it) is a singleton list [H], i.e. the same list
  • bubSort(L,SL) :- append(L1, [H1,H2|L2], L), H2 < H1, append(L1, [H2,H1|L2], NL), !, bubSort(NL,SL). : bubSort of a list, call it L, is a list, call it SL (for "sorted list"), such that there exist two adjacent elements in L which are out of order, the list NL is exactly the same as L just with those two adjacent elements swapped, and the bubSort of NL is SL
  • bubSort(L,L). : finally, if there's no two adjacent elements which are out of order, bubSort of such list is the list itself.

see also: How do I append lists in prolog?

Will Ness
  • 70,110
  • 9
  • 98
  • 181