Prolog Median

This is a team assignment.

Let L be a list containing distinct (non-repeating) integers. Moreover, assume L contains an odd number of values. Assume we want to define a Prolog predicate median(L,M) that is true when M is the median of L. One way to implement this predicate is to sort L and then extract the “middle” element of the sorted list.

A more elegant Prolog implementation, however, can be found by considering the definition of what it means for M to be L’s median: First: M must occur in L. Second: if M is used to partition L into two sublists, one containing values greater than M and the other containing values smaller than M, then the resulting sublists must be equal in length.

Use this definition to implement median(L,M). You may assume that L is always fixed as a list, but M may be a value or a variable.

FAQ from years past: You must do this assignment using the above-described technique. You may not do this assignment by first sorting the list, which isn’t nearly as much fun.

• Create a Prolog predicate partition(L,V,A,B) that partitions a list L into two lists A and B, where A contains all the items in L that are less than V, and B contains all the items in L that are greater than V. V itself is never stored in A or B.
• Use partition as defined above, and the fact that the median partitions a list into two lists of equal length, to implement median(L,M). You may assume that L is always fixed as a list, but M may be a value or a variable.

Submit your code in a file called median.pro.