Day Two was challenging. Like really hard. My imperative mindset is finding the declarative approach to coding frankly odd. When things do work it feels almost magical. And in at least one of the solutions I just chanced upon the implementation by fiddling round pretyy randomly rather than having a clear mental model of a solution beforehand. I’m not sure if I could explain the logic at all.

reverse_list.pl

Reverse the elements of a list

I spent ages trying to figure this out and came up with the first method. Then like I said above I was faffing with something else and noticed that the middle element could accumulate stuff if it was a []. So that was when I came up with reverse_list2. $ cat reverse_list.pl reverse_list([],[]). % An empty list is an empty list reverse_list([X],[X]). % A list that has one element that is identical to itself is the same. We only need to do anything complex % if there is more than one element reverse_list([Head|Tail], List) :- % there exists a function reverse_list of a List such that, splitting the list into Head and Tail reverse_list(Tail, EndTail), % calling the function on Tail and storing the result in EndTail append(EndTail,[Head],List). % and appending Head to EndTail makes a permutation of the original List % Then I thought well, I can perhaps do this, which would be mad if it worked. Which it did. We just go through swapping % our head and tail elements into a reversed array. Turns out this trick gets used a lot in Prolog. I think it is called an accumulator. % It hurts my brain though. You'd call reverse_list2([1,2,3],[],What). reverse_list2([Head|Tail], Reversed) :- reverse_list2(Tail, [Head|Reversed] ). % Then I thought its a bit ugly calling it that way. I want a two argument version so: reverse_list2(List,What) :- reverse_list2(List,[],What). % I’d love it if there were a way to make a 1 argument version, but I’ve not found that yet! charlie@mishka:~/code/seven_languages_in_seven_weeks/prolog/day_two$ cat reverse_list.pl reverse_list([],[]). % An empty list is an empty list reverse_list([X],[X]). % We only need to do anything complex % if there is more than one element reverse_list([Head|Tail], List) :- % There exists a function reverse_list of a List such that, splitting the list into Head and Tail reverse_list(Tail, EndTail), % calling the function on Tail and storing the result in EndTail append(EndTail,[Head],List). % and appending Head to EndTail makes a permutation of the original List (i.e. contains all the elements of List) % We just go through swapping our head and tail elements into % a reversed list. Turns out this trick gets used a lot in Prolog. % I think it is called an "accumulator". % You'd call reverse_list2([1,2,3],[],What). reverse_list2([Head|Tail], Reversed) :- reverse_list2(Tail, [Head|Reversed] ). % Its a bit ugly calling it that way. I want a two argument version so: reverse_list2(List,What) :- reverse_list2(List,[],What).

min_list.pl

Find the smallest element of a list.

I actually found this slightly easier than the previous excercise. Especially once I found that there was a min rule so I could say X is min(Y,Z). Only snag was that there was already a min_list in Prolog. ence cllaing this list_min. $ cat min_list.pl list_min([X],X). % if this is a single element list then the element must be the smallest element in the list list_min([Head|Tail], Min) :- % for a list with a head and tail there exists a list_min with a value min such that list_min(Tail, MinSoFar), % ( after we get and store the smallest element from the tail for comparison ) Min is min(Head, MinSoFar). % min is the smaller of either the head, or the smallest of all the tail elements

list_sort.pl

Sort the elements of a list.

This totally friend my brain. It turns out that it is possible to implement sort in Prolog. But I had no clue how. I ended up coming up with the approach of

• Shuffling the list into every possible permutation
• Checking if the Permutation is sorted

I completely realize that that is an awful way to do a sort! But my brain was pretty befuddled by this point. This search is pretty much the "naive search" described in the link. It'll work for five things, but not too many more! Well, I’ll need to study those sort algorithims some more. $ cat list_sort.pl % There is probably a nice way to sort. I don't know it. So let's try all the possible % permutations using the append trick we saw earlier. % After all premature optimization is the root of all evil and I shan't call with more % than about 4 variables. % Is there a permutation of our list such that it is true that it is sorted? list_sort(List, Sorted) :- mashup(List, Sorted), sorted(Sorted). % is a list sorted? sorted([]). % an empty list is sorted sorted([X]). % a single element list is sorted sorted([X,Y|Tail]) :- % sorted if element is<= next element X=<Y, list_sort([Y|Tail]). % Recursively % Find a possible permutations of a List. It turns out that there is a thing called perm which does this. Probably more efficiently. Took fscking ages to % work out. mashup([],[]). mashup([Head|Tail],List) :- mashup(Tail,Y), insert(Head,Y,List). % insert into List I found this function on the web. Can’t for the life % of me remember where. Thanks to the unnamed hacker for it though! insert(X,List,[X|List]). insert(X,[Head|Tail],[Head|Y]) :- insert(X,Tail,Y).

Whew! I’ll say it again. Day two was really, really hard. I’m a little bit afraid of what day three will be like!