Search code examples
prolog

Printing minimum answer as list?


I have a predicate min1([4,2,3,5],L). I want it to return the minimum number for each time the list is sent back as a tail. Example:

List       Head|Tail    Tail     L
[4,2,3,5]  [4,2,3,5]    [2,3,5]  2
[2,3,5]    [2,3,5]      [3,5]    2
[3,5]      [3,5]        [5]      3
[5]        [5]          []       5

My code:

min([X],[X]).
min([H|T],Min):-
    min(T,TMin),
    H=<TMin,
    Min is H.
min([H|T],Min):-
    min(T,TMin),
    H>TMin,
    Min is TMin.

min1([],[]).
min1([H|T],L):-
  min([H|T],R),
    write(R),
    min1(T,R). 

The problem that I am facing is with L. It does not print anything. When I use write(R), it's showing me the right result but I am unable to print it as a List in L. What should I correct?

?-min1([4,2,3,5],L).
223[5]
L = []

By removing write(R):

?-min1([4,2,3,5],L).
false

Solution

  • One of your problems is trying to understand your program using I/O. This is often not a very useful thing to do in Prolog. If you are interested in the suffixes of the list, even just for debugging, expose those suffixes as an argument of the predicate. This is much clearer than trying to print intermediate results. Because Prolog backtracks, it can be hard to understand what an intermediate result means, at what point it exists, and whether you can actually use it before backtracking makes it disappear.

    Your other problem is trying to do too much at once. Take things step by step. Prolog is a language that is well suited for decomposing problems into tiny bits. It also often forces you to decompose a problem into tiny bits.

    So, first: Enumerating a list's suffixes (including the list itself as a trivial suffix).

    list_suffix(List, List).
    list_suffix([_ | Suffix], SuffixOfSuffix) :-
        list_suffix(Suffix, SuffixOfSuffix).
    
    ?- list_suffix([4, 2, 3, 5], Suffix).
    Suffix = [4, 2, 3, 5] ;
    Suffix = [2, 3, 5] ;
    Suffix = [3, 5] ;
    Suffix = [5] ;
    Suffix = [].
    

    Then, separately, computing the minimum of a list. Your implementation is almost OK for this, the first clause needed to unwrap [X] (though it could be more efficient by using an accumulator):

    list_minimum([X], X).
    list_minimum([H | T], Min):-
        list_minimum(T, TMin),
        H =< TMin,
        Min is H.
    list_minimum([H | T], Min):-
        list_minimum(T, TMin),
        H > TMin,
        Min is TMin.
    
    ?- list_minimum([4, 2, 3, 5], Minimum).
    Minimum = 2 ;
    false.
    

    Now, and only now, we are in a position to tackle the combined problem:

    ?- list_suffix([4, 2, 3, 5], Suffix), list_minimum(Suffix, Minimum).
    Suffix = [4, 2, 3, 5],
    Minimum = 2 ;
    Suffix = [2, 3, 5],
    Minimum = 2 ;
    Suffix = [3, 5],
    Minimum = 3 ;
    Suffix = [5],
    Minimum = 5 ;
    false.
    

    You can pack this up in a predicate definition:

    list_suffix_suffixminimum(List, Suffix, SuffixMinimum) :-
        list_suffix(List, Suffix),
        list_minimum(Suffix, SuffixMinimum).
    
    ?- list_suffix_suffixminimum([4, 2, 3, 5], Suffix, SuffixMinimum).
    Suffix = [4, 2, 3, 5],
    SuffixMinimum = 2 ;
    Suffix = [2, 3, 5],
    SuffixMinimum = 2 ;
    Suffix = [3, 5],
    SuffixMinimum = 3 ;
    Suffix = [5],
    SuffixMinimum = 5 ;
    false.
    

    Maybe even without exposing the suffix:

    list_suffixminimum(List, SuffixMinimum) :-
        list_suffix(List, Suffix),
        list_minimum(Suffix, SuffixMinimum).
    
    ?- list_suffixminimum([4, 2, 3, 5], SuffixMinimum).
    SuffixMinimum = 2 ;
    SuffixMinimum = 2 ;
    SuffixMinimum = 3 ;
    SuffixMinimum = 5 ;
    false.
    

    Now, and only now that the problem has been solved, you can add I/O if you feel like it. Although at this point, why would you?