Totally bored and jobless over this surprisingly silent weekend, I decided to revisit some of the Haskell programs that I had written when I took the Functional programming course during the previous year. While I was at it, I remembered this particular topic which struck me as interesting back then (..and it still is). So I am going to write about it despite the fact that it is something that would be covered by any basic Haskell textbook or tutorial. Well, that just goes to show how jobless I am!
The first time we were asked to reverse a list in Haskell, I did it using the extremely straightforward method I could think of.
revList :: [a] -> [a]
revList [] = []
revList (x:xs) = (revList xs) ++ [x]
What we are doing here is, given a list of the form (x:xs) where x is the element at the head of the list and xs is the tail of the list (which is again a list!). We recursively apply revList to the tail and then concatenate the result with the singleton list containing the head x.
Turns out this really bad way of reversing a list.
Let us analyse why.
One of the ways of looking at a Haskell list, say [x,y,z,w] is
x:(y:(z:(w:[]))), reflecting the head:tail pattern mentioned earlier.
Observe that to append the element x at the end of the reversed list, we concatenate the reversed list with the singleton list [x]. Now, the concatenation of two lists even in Haskell is at best a linear time operation. One could think of a way of concatenating lists as follows
(++) :: [a] -> [a] -> [a]
(++) [] l = l
(++) (x:xs) l = x:((++ ) xs l)
Thus the concatenation operation would have to walk to through the first list at least once.
Let 
Thus
The reason for this is the fact that appending a single element to a list takes linear time proportional to the length of the list. This is due to the manner in which lists are internally represented in Haskell.
However, adding an element to the head of the list is a constant time operation. The code for doing this would look something like:
add_to_head :: Int -> [Int] -> [Int]
add_to_head x l = (x:l)
Thus, given a list (x:(y:(z:(w:[])))) appending, say an element v to the head would amount to storing the list as v:(x:(y:(z:(w:[])))). Thus we don’t have to worry about the length of the list. In this sense, the Haskell list is similar to a stack. Adding an element to the top or removing an element from the top is a constant time operation. But adding to the bottom requires popping out all the elements, pushing this new element, and pushing all the elements (ok, lists do better than that.)
So, we can make use of this fact to optimize revList so that the operation takes linear time proportional to the length of the list. And the optimization would involve same trick that is used in reversing a stack. i.e pop out the element at head of the stack, push it into another stack, and repeat this till the first stack is empty. This requires only linear time.
listRevFast :: [a] -> [a]
listRevFast l = _listRevFast l []
where
_listRevFast :: [a] -> [a] -> [a]
_listRevFast [] l = l
_listRevFast (x:xs) l = _listRevFast xs (x:l)
And this one, you can verify requires linear time since it accesses each element of the original list exactly once.
the set of all finite words over 
. The set of all infinite words over 
.
let 
denote the set of all prefixes of 
, we define the Limit Language of 
to be the subset of 
, there is a totally ordered (with respect to the prefix ordering) infinite subset 
of 
where 
.
‘s. And so, we can write 
.
, we have 
. Since 
in 
.
, then we can find a 
such that 
. Now for 
we can find a 
. We can similarly find 
such that each prefix of the form 
of the infinite string 
is in 
are in 
]
where 
and
.
is an infinite set.
. Since 
s, it is not in 
contradicting our assumption.
support seems to work just fine. However, I need to check if there’s an easy way to write code snippets.
