was stock

Code Snippets in Google Results

I’ve just noticed that code snippets are appearing in the search results in google. The code snippets come from code search division of Google labs.

Although this is pretty cool, will it add any value to the search results? Usually when you google for the a function more often that not you are looking for the parameters, return value or the behavior of this function. One thing that if will add is that users will be able to look at quality code. Google for sprintf, sscanf and printf and you will see code snippets from some really beautiful code. They show you the proper way to comment, structure and name your variables.

Posted in Google | No Comments »

Problem #10 Run-length encoding of a list.

let pack plist =
 let rec rec_pack rest packed acc a =
  match rest with
  [] -> ( packed @ [acc] )
  |x::xs ->
           if ( x = a ) then
            ( rec_pack xs packed ( x :: acc ) a)
           else
            ( rec_pack xs ( packed @ [acc] ) [x] x)
 in match plist with
 [] -> []
 | y::ys -> ( rec_pack ys [] [y] y);;
 let encode l =
	List.map
		( fun a -> ( List.length a, List.hd a ) )
		( pack l );;
if ((encode ['a';'a';'a';'a';'a';'a';'b';'b';'b';'b';'a';'a';'a';'b';'b';'c';'d';'d';'d';'d';'d';'d';'e']) =
     ([(6,'a');(4,'b');(3,'a');(2,'b');(1,'c');(6,'d');(1,'e');]))
then ( Printf.printf "okn" )
else ( Printf.printf "failedn" );;

It’s easier to reuse code, then reinvent some of the code. This case I used the solution for problem #9 and used the map function to create a new list. The List.map function is incredibly useful. Just ask Google with their Map Reduce

Posted in 99 problems, F# | No Comments »

Problem #9 Pack consecutive duplicates of list elements into sublists.

#light
let pack plist =
 let rec rec_pack rest packed acc a =
  match rest with
  [] -> ( packed @ [acc] )
  |x::xs ->
           if ( x = a ) then
            ( rec_pack xs packed ( x :: acc ) a)
           else
            ( rec_pack xs ( packed @ [acc] ) [x] x)
 in match plist with
 [] -> []
 | y::ys -> ( rec_pack ys [] [y] y);;
if
( ( pack ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"] ) = [["a";"a";"a";"a"];["b"];["c";"c"];["a";"a"];["d"];["e";"e";"e";"e"]] )
then
( Printf.printf "okn" )
else
( Printf.printf "failedn" );;

The code has nothing new seen in previous problems but it may be tricky to read. What the inner recursive function is doing is holding the element that RLE is happening in the variable a. It keeps appending a into acc (accumulator) until it sees a different element. Then it takes the sublist and appends into tha variable packed. The variable names may not be great but this gets the job done.

Posted in 99 problems, F# | No Comments »

Problem #8 Eliminate consecutive duplicates of list elements.

This problem was a bit harder than usual. A couple of things were learned from doing this problem. Using [] to enclose an a’ type while get rid of type mismatch errors. Another development tip is to build the inner recursive function first and then make the wrapper function.

let compress_list clist =
  let rec rec_compress_list head tail =
   match tail with
   | [] -> []
   | (y::ys) ->  if [y] = [head] then
                   rec_compress_list y ys
                 else
                   [head] @ (rec_compress_list y ys)
 in match clist with
   | [] -> clist
   | (y::ys) -> (rec_compress_list y ys);;

Here are some test cases.

['a';'a';'a';'a';'a';'a';'b';'b';'b';'b';'a';'a';'a';'b';'b';'c';'d';'d';'d';'d';'d';'d';'e'] |> compress_list |> List.iter (printf "[%c]") ;
printf "n";
['a';'b';'b';'b';'b';'a';'a';'a';'b';'b';'c';'d';'d';'d';'d';'d';'d';'e'] |> compress_list |> List.iter (printf "[%c]") ;

–Update

Joel Lanciaux was kind enough to point out a bug. Apparently my function was chopping off the last element. D’oh!

Here is the updated solution

let compress_list clist =
  let rec rec_compress_list head tail =
   match tail with
   | [] -> [head]
   | (y::ys) ->  if [y] = [head] then
                   rec_compress_list y ys
                 else
                   [head] @ (rec_compress_list y ys)
 in match clist with
   | [] -> clist
   | (y::ys) -> (rec_compress_list y ys);;

Posted in 99 problems, F# | 2 Comments »

Problem #7

Flatten a nested list structure.

This solution builds off the last one in that you need to to recursively match the your result so far and tail recursively add the the rest of the result.

let rec flatten_list slist =
   match slist with
   | [] -> []
   | y::ys -> y @ flatten_list ys

There was not much to it. As you can see with the test case.

[["a";"b"];["c"];["e"]] |> flatten_list |> List.iter (printf "[%s]") ;

flatten_list’s type definition is (’a list list -> ‘a list) So that means it takes in ‘a list list and returns ‘a list.

In the test case [”a”;”b”];[”c”];[”e”] is in fact a list of ‘a lists. [”e”] is still a list, just a list of a single element. Since the type definition is (’a list list -> ‘a list), we can use a different type for ‘a

Such as

[["a";"b"];["c"];["e"]] |> flatten_list |> List.iter (printf "[%d]") ;

*Note* that we didn’t to change printf just for printing purposes.

Posted in 99 problems, F# | No Comments »

Problem #6

You can reverse the list and then match it to the original or try to solve it how humans actually check if a string is a palindrome. That is by simultaneously scanning the string from left to right and right to left char by char checking if they match. The only thing new is the true and false keyword.

Also make sure your bounds on the list are set correctly and this problem can be broken up into three base cases.

1) low < high

This means we are still scanning the string. We match the corresponding char and check if they are equal. If they are not, its not a palindrome and return false. If they are recursive call the function moving the bounds by 1.

1) low = high

Well if low = high that means that they are pointing at the same char and therefore can return true since the recursive function would had caught a case where the scanning did not match chars. This string is also of odd length.

3) low > high

This happens when the bounds cross each from the recursive calls. Only happens with strings of equal length. Case 1 would had caught the string by now if it wasn’t a palindrome, thus it is safe to return true.

let is_palindrome (listy : List<char>) =
  let rec is_palindrome_rec (list : List<char>) low high =
     if (low = high) then
       true
     elif (low < high) then
       if (List.nth list low) = (List.nth list high) then
         is_palindrome_rec list (low + 1) (high - 1)
       else
         false
     else true
  in is_palindrome_rec listy 0 (List.length listy - 1)

Notice the elif keyword which is equal to else if. Some optimization can lead to

let is_palindrome (listy : List<char>) =
  let rec is_palindrome_rec (list : List<char>) low high =
     if (low < high) then
       if (List.nth list low) = (List.nth list high) then
         is_palindrome_rec list (low + 1) (high - 1)
       else
         false
     else true
  in is_palindrome_rec listy 0 (List.length listy - 1)

Since case 2 and 3 return the same result. Of course reversing the list and comparing it to the original is a lot smarter, efficient and faster way of doing this but at least this way you may struggle a bit and learn a bit more.

Some test cases.

if ( is_palindrome ['a';'b';'c';'d';'e'] )
     then ( Printf.printf "Failed!" )
else ( Printf.printf "Success!" );;

if ( is_palindrome ['a';'b';'c';'b';'a'] )
     then ( Printf.printf "Success!" )
else ( Printf.printf "Failed!" );;

Posted in 99 problems, F# | No Comments »

Problem #5

Similiar solution to problem #4, I used recursion to reverse the list.

 let rec reverse_list l =
   match l with
      | [] -> []
      | (x::xs) -> (reverse_list xs) @ [x];;
 myList |> reverse_list |> List.iter (printf "[%d]") ;;

The (x:xs), @ and [] symbols are necessary so that it compiles correctly.

Posted in 99 problems, F# | No Comments »

Problem #4

This also can be done using using one of the built functions but lets try to do this using recursion.

let rec nr_elements l =
     match l with
     | [] -> 0
     | x::xs -> 1 + nr_elements xs;;

nr_elements myList |> printf "Length: %d"

Just use forward recursion adding one to the result and then return zero at the base case (empty list).

Posted in 99 problems, F# | No Comments »

Problem #3

So the problem can be trivial using List.nth so I can go ahead and use that as my solution. But where is the fun in that?

Let’s try and learn something. We are not trying to be efficient, we are trying to learn something.

This will be a good place to start using recursion. The thing with functional programming is that you have to use a keyword to tell the compiler that this function is going to be called within the function itself.

So lets start off with the basic skeleton of a recursive function that iterates through a list.

#light
let rec p03 list =
    match list with
    | y::ys -> p03 ys
    | []    -> []

The “rec” tells the compiler, that this function is recursive. The match list with is used to type match the list. The list is either empty or has some elements.

#light
let rec p03 list k =
    match list with
    | y::ys -> (match k with
                | 1 -> y
                | _ -> if (k > 1) then p03 ys (k - 1)
                       else y)
    | []    -> []

This statement just adds another match statement within the first case. Also note the |_ ->, this tells the compiler for any other values go to this case. Then just a simple if else statement to catch negative numbers and this problem is solved.

Also as a general note, don’t use tabs with #light, it took me a while to figure this out.

Posted in 99 problems, F# | No Comments »

Problem #2

The second problem seems a lot like number 2.

// Problem 02: Find the last but one element of a list

// last_but_one(X,L) :- X is the last but one element of the list L
//    (element,list) (?,?)

#light
let thisList = [1; 2; 3; 4; 5; 6]
let l = List.length thisList
List.nth thisList (l - 2)
     |> printf "Answer: %d"  

I still haven’t really seen an F# tutorial. I am not bragging, I am apologizing since my solution is no where as refined and as elegant as the solutions that got posted at Frickensweet. I think I am doing myself a bad service by not reading up on F#. So I intend on at least reading up on the tutorials before going on.

Posted in 99 problems, F# | No Comments »