undefined | Better HN

0 pointsnandemo14y ago0 comments

FWIW, in my Programming Languages Theory class the first sorting algorithm we learned for Prolog was Permutation sort, which is a better version of Bogosort. Instead of trying a random permutation each time, Permutation sort will try each permutation once. In Prolog, this is a (the?) naive sort.

The code below consists of declaring that S is a sorted version of L as long as S is a permutation of L and S is sorted.

  permutation_sort(L,S) :- permutation(L,S), sorted(S).

  sorted([]).
  sorted([_]).
  sorted([X,Y|ZS]) :- X =< Y, sorted([Y|ZS]).

  permutation([],[]).
  permutation([X|XS],YS) :- permutation(XS,ZS),select(X,YS,ZS).

0 comments

sevenproxies14y ago

permutation([X|XS],YS) :- permutation(XS,ZS),select(X,YS,ZS).

Where is ZS defined? Bear in mind that I only took half a module's worth (6 modules in a year at my university) of Prolog and we really just used it for learning predicate logic.

Nevertheless, using Prolog (especially when my code worked!) blew my mind. In the assignment I had to write a program that mimicked part of an aircraft controller in that each aircraft in it's flightplan had to be separated from all other aircraft. Do you think Prolog will ever become popular (perhaps with the incoming Semantic web) or is it destined for academic work and system proofs only?

sesqu14y ago

ZS is defined by select.

I don't believe Prolog will become any more popular than it is. The Japanese had some sort of a government project a few years ago, but I think that fell through. Now we have Erlang, Haskell and Java libraries that replicate most functionality, and then some.

j / k navigate · click thread line to collapse