haskell

You are currently browsing articles tagged haskell.

Programming Language Popularity – Part Four

September 22, 2011 in programming, software | Add a comment

I compiled some programming language popularity statistics in April 2009, October 2009 and October 2010 . Here’s an update for September 2011:

I made a number of Google searches of the forms below and summed the results (previous posts averaged the results):

"implemented in <language>"
  "written in <language>"

Naturally this is of very limited utility, and the numbers are only useful when comparing relatively within the same search since the number of results Google returns can vary greatly over time.

Language Total Prev. Position Position Delta
C 10,360,000 2 1
PHP 10,351,000 1 -1
C++ 6,495,000 3 0
Python 5,759,000 5 1
C# 5,335,000 4 -1
 
Java 4,890,000 8 2
Perl 3,702,000 6 -1
JavaScript 3,077,000 7 -1
Ruby 1,654,000 9 0
Lisp Family1 1,022,870 11 1
 
FORTRAN 975,600 10 -1
Tcl 594,500 12 0
Lisp 486,000 14 1
Haskell 450,500 16 2
Erlang 419,700 13 -2
 
Lua 367,100 18 2
ML Family2 348,400 17 0
COBOL 308,270 15 -3
Common Lisp 254,900 19 0
OCaml 240,300 21 1
 
Prolog 224,000 20 -1
Scala 203,400 23 1
Scheme 184,700 22 -1
Smalltalk 129,700 24 0
Clojure 84,600 27 2
 
(S)ML3 83,630 25 -1
Forth 69,980 26 -1
Caml 24,470 28 0
Io 17,700 30 1
Arc 12,670 29 -1

1 combines Lisp, Scheme, Common Lisp, Arc & Clojure
2 combines OCaml, (S)ML, Caml
3 summed separate searches for sml and ml

Tags: , , , , , , , , , , , ,

Find Longest Substring Palindrome in Haskell

March 13, 2011 in programming | 7 comments

I stumbled upon a programming challenge a company was using for recruitment purposes and thought I’d create a Haskell solution as a learning exercise. The first problem was to find the longest palindrome embedded in a text string.

The following Haskell solution seems very readable to me, but it’s a naive solution that’s inefficient. It computes an answer on my 2.6 year old Macbook Pro in under 4 seconds, but a 2x increase in text requires a 7x increase in CPU time.

I believe there are algorithms to find the longest embedded palindrome in linear time, so I may post a refinement later.

-- Find the longest palindrome in a text string.

module Main where
import Char

text = "I'll just type in some example text here and embed a little \
\palindrome - A man, a plan, a canal, Panama! - I expect that will be \
\the longest palindrome found in this text.\
\Lorem ipsum dolor sit amet, consectetur adipiscing elit.\
\Integer volutpat lorem imperdiet ante bibendum ullamcorper. Mauris \
\tempor hendrerit justo at elementum. Vivamus elit magna, accumsan id \
\condimentum a, luctus a ipsum. Donec fermentum, lectus at posuere \
\ullamcorper, mauris lectus tincidunt nulla, ut placerat justo odio sed\
\ odio. Nulla blandit lorem sit amet odio varius nec vestibulum ante \
\ornare. Aliquam feugiat, velit a rhoncus rutrum, turpis metus pretium \
\dolor, et mattis leo turpis non est. Sed aliquet, sapien quis \
\consequat condimentum, sem magna ornare ligula, id blandit odio nisl \
\vitae erat. Nam vulputate tincidunt quam, non lacinia risus tincidunt \
\lacinia. Aenean fermentum tristique porttitor. Nam id dolor a eros \
\accumsan imperdiet. Aliquam quis nibh et dui ultricies cursus. Nunc \
\et ante non sapien vehicula rutrum. Duis posuere dictum blandit. Nunc \
\vitae tempus purus."

clean = map toLower . filter isAlpha

palindrome str = str == reverse str

substrings []     = []
substrings (x:xs) = substrings' (x:xs) ++ substrings xs where
  substrings' []     = []
  substrings' (y:ys) = [y] : [ (y:s) | s <- substrings' ys ]

longest []     = []
longest (x:xs) = if length x > length max then x else max
  where max = longest xs

longest_palindrome xs =
  longest (filter palindrome (substrings (clean text)))

main = print (longest_palindrome text)

As a comparison, I translated the program into Ruby. I program predominantly in Ruby these days, and I like it, but the Ruby version is 25 times slower (98 sec. vs. 4 sec.), and it’s 2.4 times more lines of code (31 vs. 13 – excluding the text).

A gain in runtime efficiency, expressive power and multi-core capability is very attractive!

I’m using Ruby 1.9.2 and GHC 6.12.3 on Mac OS X 10.5.8 on a 2.4 GHz Core 2 Duo w/ 4 GB RAM.

ruby 1.9.2p0 (2010-08-18 revision 29036) [i386-darwin9.8.0]
Glasgow Haskell Compiler, Version 6.12.3, for Haskell 98, stage 2 booted by GHC version 6.12.2

TEXT = <<END
I'll just type in some example text here and embed a little
palindrome - A man, a plan, a canal, Panama! - I expect that will be
the longest palindrome found in this text.
Lorem ipsum dolor sit amet, consectetur adipiscing elit.
Integer volutpat lorem imperdiet ante bibendum ullamcorper. Mauris
tempor hendrerit justo at elementum. Vivamus elit magna, accumsan id
condimentum a, luctus a ipsum. Donec fermentum, lectus at posuere
ullamcorper, mauris lectus tincidunt nulla, ut placerat justo odio sed
 odio. Nulla blandit lorem sit amet odio varius nec vestibulum ante
ornare. Aliquam feugiat, velit a rhoncus rutrum, turpis metus pretium
dolor, et mattis leo turpis non est. Sed aliquet, sapien quis
consequat condimentum, sem magna ornare ligula, id blandit odio nisl
vitae erat. Nam vulputate tincidunt quam, non lacinia risus tincidunt
lacinia. Aenean fermentum tristique porttitor. Nam id dolor a eros
accumsan imperdiet. Aliquam quis nibh et dui ultricies cursus. Nunc
et ante non sapien vehicula rutrum. Duis posuere dictum blandit. Nunc
vitae tempus purus.
END

def clean str
  str.gsub(/[^A-Za-z]/,'').downcase
end

def palindrome? str
  str == str.reverse
end

def subs str
  return [] if str.empty?
  y = str[0,1]
  subs(str[1..-1]).inject([y]) do |result, s|
    result << y + s
    result
  end
end

def substrings str
  return [] if str.empty?
  subs(str) + substrings(str[1..-1])
end

def longest strs
  strs.inject("") do |max, str|
    max = str if str.length > max.length
    max
  end
end

def longest_palindrome str
  longest(substrings(clean(str)).inject([]) {|result, str|
            result << str if palindrome?(str)
            result
          })
end

puts longest_palindrome(TEXT)

Update 3/13/11 19:30
Rick’s comment (see his blog post linked to in his comment) regarding the importance of algorithm choice is certainly a valid one – a better algorithm in a slower language may win over an inferior algorithm in a faster language (for large enough datasets). However, what I’m becoming interested in is the fact that one may gain both productivity/power and runtime speed by making wise programming language choices.

In the case of an interpreted language such as Ruby, it’s helpful to “stay in C code” as much as possible. In other words, to favor built-in library routines that have been implemented in C over hand written Ruby code. As much as I like Ruby, this is one of the things that bothers me – the fact that the Ruby code written by the programmer is vastly inferior in performance to the built-in library routines.

I wasn’t planning on refining the Haskell version this soon, but after seeing Rick’s blog post response, I couldn’t resist :)

I should first provide some background info for context. When I wrote the original Haskell version above, I was in the middle of an online programming challenge, and my goal was simply to compute the answer in a reasonable amount of time to move on to the next challenge, so the brief, easily understandable, Haskell version worked great. Hence, my disclaimers in the post regarding the naivity and inefficiency of the solution. The Ruby code in this post was an afterthought simply to see a comparison between identical algorithms. Given that apple & apple comparison, I’m impressed with the brevity and speed of the Haskell version.

Since I’m still very much a Haskell newbie, and short on time, I found an incredible solution by Johan Jeuring. It’s a little bit longer than the Ruby version, but much, much faster. It’s so fast, I had to increase the input quite a bit to get a reasonable comparison – I replicated the original text 23 times and reversed one of the replications to make a fairly long palindrome.

Rick’s Ruby version took 169.4 seconds, Johan’s Haskell version took 0.032 seconds. In other words, Ruby takes over 5,000 times as long to compute the result. Clearly this is an apples and oranges comparison, but I fully expect that a Ruby version using an identical algorithm will take 100 times as long (or longer) to run and would be less concise. Giving up runtime performance to gain programmer power is one thing, but giving up runtime performance and power is a tough pill to swallow.

Here is a slightly modified version of Johan Jeuring’s code. He was also kind enough to provide his code here:

-- Reorganized from Johan Jeuring's solution:
module Main where
import Data.List (maximumBy,intersperse)
import Data.Char
import Data.Array 

text = "I'll just type in some example text here and embed a little \
\palindrome - A man, a plan, a canal, Panama! - I expect that will be \
\the longest palindrome found in this text.\
\Lorem ipsum dolor sit amet, consectetur adipiscing elit.\
\Integer volutpat lorem imperdiet ante bibendum ullamcorper. Mauris \
\tempor hendrerit justo at elementum. Vivamus elit magna, accumsan id \
\condimentum a, luctus a ipsum. Donec fermentum, lectus at posuere \
\ullamcorper, mauris lectus tincidunt nulla, ut placerat justo odio sed\
\ odio. Nulla blandit lorem sit amet odio varius nec vestibulum ante \
\ornare. Aliquam feugiat, velit a rhoncus rutrum, turpis metus pretium \
\dolor, et mattis leo turpis non est. Sed aliquet, sapien quis \
\consequat condimentum, sem magna ornare ligula, id blandit odio nisl \
\vitae erat. Nam vulputate tincidunt quam, non lacinia risus tincidunt \
\lacinia. Aenean fermentum tristique porttitor. Nam id dolor a eros \
\accumsan imperdiet. Aliquam quis nibh et dui ultricies cursus. Nunc \
\et ante non sapien vehicula rutrum. Duis posuere dictum blandit. Nunc \
\vitae tempus purus."

clean = map toLower . filter isAlpha

longestPalindrome input =
  let inputArray      =  listArrayl0 input
      (maxLength,pos) =  maximumBy
                            (\(l,_) (l',_) -> compare l l')
                            (zip (palindromesAroundCentres inputArray) [0..])
  in showPalindrome inputArray (maxLength,pos)

longestPalindromes m input =
  let inputArray =  listArrayl0 input
  in concat $ intersperse "\n"
            $ map (showPalindrome inputArray)
            $ filter ((m<=) . fst)
            $ zip (palindromesAroundCentres inputArray) [0..]

lengthLongestPalindrome :: String -> String
lengthLongestPalindrome = show . maximum . palindromesAroundCentres . listArrayl0

lengthLongestPalindromes :: String -> String
lengthLongestPalindromes = show . palindromesAroundCentres . listArrayl0

palindromesAroundCentres a =
  let (afirst,_) = bounds a
  in reverse $ extendTail a afirst 0 []

extendTail a n currentTail centres
  | n > alast = finalCentres currentTail centres
                   (currentTail:centres)
  | n-currentTail == afirst =
      extendCentres a n (currentTail:centres)
                    centres currentTail
  | a!n == a!(n-currentTail-1) =
      extendTail a (n+1) (currentTail+2) centres
  | otherwise =
      extendCentres a n (currentTail:centres)
                    centres currentTail
  where  (afirst,alast)  =  bounds a

extendCentres a n centres tcentres centreDistance
  | centreDistance == 0 =
      extendTail a (n+1) 1 centres
  | centreDistance-1 == head tcentres  =
      extendTail a n (head tcentres) centres
  | otherwise =
      extendCentres a n (min (head tcentres)
                    (centreDistance-1):centres)
                    (tail tcentres) (centreDistance-1)

finalCentres 0     _        centres  =  centres
finalCentres (n+1) tcentres centres  =
  finalCentres n
               (tail tcentres)
               (min (head tcentres) n:centres)
finalCentres _     _        _        =  error "finalCentres: input < 0"               

showPalindrome a (len,pos) =
  let startpos = pos `div` 2 - len `div` 2
      endpos   = if odd len
                 then pos `div` 2 + len `div` 2
                 else pos `div` 2 + len `div` 2 - 1
  in show [a!n|n <- [startpos .. endpos]]

listArrayl0 string  = listArray (0,length string - 1) string

sampleText s = concat (replicate 8 s ++ [ "x" ] ++ [ reverse s ] ++ replicate 14 s)

main = print (longestPalindrome (clean (sampleText text)))

Here's the relevant change to Rick's Ruby version:


def sample_text str
  str * 8 + 'x' + str.reverse + str * 14
end

puts clean(sample_text(TEXT)).longest_palindrome

Tags: ,

Cracker Barrel Peg Board Puzzle in Haskell

March 10, 2011 in programming | 1 comment

I first wrote a program to solve the Cracker Barrel peg board puzzle (15 holes arranged in a triangle with 14 golf tees) many years ago as youth using the BASIC language. I wish I still had the source to that, because I’m pretty sure this Haskell version would kick its butt :)

I’m still trying to get my head around Haskell, so I expect there are many possible improvements to this program, but even so, I’m pleased with how Haskell allows me to express logic.

-- Solve the Cracker Barrel Peg Board Puzzle

module Main where

type Pos = (Int, Int)
type Move = (Pos, Pos)
type Board = [ Pos ]

isOccupied b p = elem p b
isEmpty b p    = not (isOccupied b p)
isPos (r,c)    = elem r [0..4] && elem c [0..r]

-- Possible moves for one position
positionMoves b p = [ (p, dst) | (neighbor, dst) <- pairs,
                      isOccupied b neighbor &&
                      isEmpty b dst ]
  where (r, c) = p
        pairs  = filter (\(p1,p2) -> isPos p1 && isPos p2)
                   [ ((r + or `div` 2, c + oc `div` 2),(r + or, c + oc)) |
                     (or, oc) <- [ (-2,0), (0,2), (2,2), (2,0), (0,-2), (-2,-2) ] ]

-- Possible moves for all positions on the board
possibleMoves b = concat [ positionMoves b pos | pos <- b ]

-- Make a move and return the new board
move b (src,dst) = dst:filter pred b
  where ((sr,sc),(dr,dc)) = (src,dst)
        neighbor = (div (sr+dr) 2, div (sc+dc) 2)
        pred     = \pos -> (pos /= src) && (pos /= neighbor)

-- Make moves until the goal position is met
play b p moves =
  if null nextMoves then
    if length b == 1 && head b == p then reverse moves else []
  else
    tryMoves nextMoves
  where
    nextMoves       = possibleMoves b
    tryMoves []     = []
    tryMoves (m:ms) =
      let result = play (move b m) p (m:moves)
      in if null result then tryMoves ms else result

-- Compute the initial empty position to know the goal, then solve the puzzle
solve b = let emptyPos = head [ (r,c) | r <- [0..4], c <- [0..r], isEmpty b (r,c) ]
          in play b emptyPos []

-- A sample board with the topmost hole empty
board :: Board
board = [ (1,0), (1,1),
          (2,0), (2,1), (2,2),
          (3,0), (3,1), (3,2), (3,3),
          (4,0), (4,1), (4,2), (4,3), (4,4) ]

main = print (solve board)

Tags:

Programming Language Popularity – Part Three

October 8, 2010 in programming | 1 comment

I compiled some programming language popularity statistics in April 2009 and October 2009 . Here’s an update for October 2010:

I made a number of Google searches of the forms below and averaged the results:

"implemented in <language>"
  "written in <language>"

Naturally this is of very limited utility, and the numbers are only useful when comparing relatively within one column since the number of results Google returns can vary greatly over time.

Language Apr 2009 Oct 2009 Oct 2010 Position Delta
PHP 680,000 5,083,500 14,096,000 +3
C 1,905,500 16,975,000 9,675,000 -1
C++ 699,000 6,270,000 6,510,000 -1
C# 349,700 2,125,000 5,132,000 +4
Python 396,000 3,407,000 5,114,500 +1
Perl 365,500 3,132,500 4,675,000 +1
JavaScript 102,700 1,163,000 2,120,000 +4
Java 850,000 5,118,000 1,495,500 -5
Ruby 99,650 227,000 1,426,000 +13
FORTRAN 1,621,000 770,850 0
Lisp Family1 176,507 3,489,650 399,685 -6
Tcl 44,800 382,000 313,400 +5
Erlang 22,285 161,700 188,800 +12
Lisp 61,900 486,500 174,050 +1
COBOL 247,300 166,435 +6
Haskell 22,550 280,500 157,150 +4
ML Family2 29,062 1,003,800 149,005 -5
Lua 13,065 131,800 128,150 +9
Common Lisp 20,600 554,500 112,750 -5
Prolog 17,750 390,500 100,000 -4
OCaml 22,000 343,500 99,050 -3
Scheme 86,450 2,100,000 82,650 -13
Scala 3,570 66,250 65,950 +6
Smalltalk 9,105 187,500 56,950 0
(S)ML3 5,173 590,700 42,130 -12
Forth 6,465 146,450 25,880 0
Clojure 782 62,200 23,525 +3
Caml 1,889 69,600 7,825 0
Arc 6,775 286,500 6,710 -10
Io 1,760 198,500 3,025 -7

1 combines Lisp, Scheme, Common Lisp, Arc & Clojure
2 combines OCaml, (S)ML, Caml
3 summed separate searches for sml and ml

Tags: , , , , , , , , , , , ,

Programming Language Popularity – Part Two

October 24, 2009 in programming | Add a comment

I compiled some programming language popularity statistics in April and mentioned I’d update the results in 6 months, so here they are:

I made a number of Google searches of the forms below and averaged the results:

"implemented in <language>"
"written in <language>"

Language # Results
Apr 09		 # Results
Oct 09		 Position
Delta
C 1,905,500 16,975,000 0
C++ 699,000 6,270,000 +1
Java 850,000 5,118,000 -1
PHP 680,000 5,083,500 0
Lisp Family1 176,507 3,489,650 +3
Python 396,000 3,407,000 -1
Perl 365,500 3,132,500 -1
C# 349,700 2,125,000 -1
Scheme 86,450 2,100,000 +2
FORTRAN 1,621,000 N/A
JavaScript 102,700 1,163,000 -1
ML Family2 29,062 1,003,800 +3
(S)ML3 5,173 590,700 +12
Common Lisp 20,600 554,500 +5
Lisp 61,900 486,500 -2
Prolog 17,750 390,500 +4
Tcl 44,800 382,000 -3
OCaml 22,000 343,500 0
Arc 6,775 286,500 +4
Haskell 22,550 280,500 -4
COBOL 247,300 N/A
Ruby 99,650 227,000 -10
Io 1,760 198,500 +6
Smalltalk 9,105 187,500 -1
Erlang 22,285 161,700 -7
Forth 6,465 146,450 -1
Lua 13,065 131,800 -5
Caml 1,889 69,600 0
Scala 3,570 66,250 -2
Clojure 782 62,200 0

1 combines Lisp, Scheme, Common Lisp, Arc & Clojure
2 combines OCaml, (S)ML, Caml
3 summed separate searches for sml and ml

Tags: , , , , , , , , , , , , , , , , , , , ,

Haskell In The Finals

August 18, 2009 in programming | 3 comments

As I explain in 2009 Programming Language Plan, I’ve been in the process of evaluating programming languages to determine their suitability for use in my work. I’ve been proceeding on two fronts – statically typed functional programming languages and the venerated Lisp family.

Haskell The Hope Of The Statically Typed Family

After many hours of research and a brief dive into Standard ML, I’ve selected Haskell as the best candidate for me to evaluate statically typed functional programming languages. At this point, I’m subjectively biased against statically typed functional programming languages because of the enjoyment and productivity I’ve found in Ruby & Lisp, but my only experience with statically typed languages (C, C++, Java) has not been representative of good statically typed languages, so I’m reluctant to form a strong opinion of static typing before I’ve become proficient in a good statically typed language.

There are, of course, a number of respected statically typed functional programming languages, but I think Haskell provides me with the best opportunity to make a personal assessment regarding the benefits of static typing for my particular situation, and I think someone would be hard pressed to convince me that it’s a poor choice objectively.

There Can Be Only One

After working halfway through Programming in Standard ML by Robert Harper, I realized that I enjoy the language and it seems simpler & cleaner than Haskell, but I also realized that I only have time to become truly proficient in one statically typed functional programming language in the near future. I feel that a reasonable level of proficiency is required to evaluate a language well. I have seen many examples of someone, with only a little knowledge of a programming language, making an unfounded criticism of a programming language, or a particular feature, only to be corrected with an accurate, elegant and convincing counter argument by someone who is experienced with the language.

A quick survey of a language won’t be enough for me to make a decision on some key points such as static vs. dynamic, nonstrict vs. strict, pure vs. impure, etc. as well as important peripheral issues such as existing libraries, tools, etc. – it’s going to require understanding some of the subtleties of the language and writing enough code to get a feel for the language, so I felt I needed to limit my choice to one statically typed FPL.

Static vs. Dynamic

Clearly both static and dynamic typing work well for large numbers of people. One of my goals is simply to answer the static vs. dynamic question for myself given my preferences and the type of software I want to develop. I’d previously decided to learn both Standard ML and Haskell, so my reasons below for choosing Haskell are primarily with respect to comparing the two languages:

Haskell Is Pure And Lazy

I’m already familiar with impure, or multi-paradigm, programming languages that offer some functional features but allow imperative programming, so being forced to program in a purely functional manner and abandon my comfort zone of imperative patterns is an advantage for me. I have no experience with lazy languages, so Haskell offers an opportunity to gain more experience with laziness :).

In some respects, Haskell is more different than Lisp compared to other statically typed functional programming languages, so it’s a good point of comparison. It may end up being the ultimate death match :)

  • Static vs. Dynamic
  • Nonstrict vs. Strict
  • Rich/Complex Syntax vs. Simpler Syntax
  • Pure vs. Impure/Multi-paradigm

Active Community

Haskell has a very active community. Although I’m skeptical about whether a statically typed functional programming language will be suitable for the type of work I want to do with it, it makes sense to choose one that has a reasonable shot, and I don’t personally feel that Standard ML does – it was mainly to be an introduction to functional programming and a stepping stone to another FPL.

Part of the reason I don’t feel that Standard ML has a reasonable shot is that it feels dated and somewhat abandoned. Functional programming languages are niche languages to begin with, but it seems that Haskell and OCaml both have fairly strong communities.

Cool Features

Although I think Haskell’s custom of continuing to add cutting edge research features into the language may have some disadvantages if not done well, i.e. making the language messier and complicated, for my primary purpose of evaluating the benefits of statically typed languages, I think having more advanced features is an advantage over Standard ML. If a language with such an active research community as Haskell fails to convince me of the benefits of static typing, then it may just not be for me.

Monads and type classes seem interesting, and Haskell provides an opportunity to learn them. Monads seem useful outside of Haskell, so the time spent learning about them can be leveraged. I already like list comprehensions, so it’s nice to have them available again.

Learning some of the advanced features of Haskell will be beneficial to me regardless of whether I continue programming in Haskell or decide to go with the Lisp family.

Textual Resources

Standard ML actually has a surprising number of good texts available, so I don’t think Haskell offers a big advantage here, but in my particular case, I already own two Haskell texts – Programming in Haskell by Graham Hutton and The Craft of Functional Programming by Simon Thompson. Also, Chris Okasaki’s Purely Functional Data Structures provides Haskell examples as does Richard Bird’s Introduction to Functional Programming using Haskell (2nd ed.). Lastly, I think Real World Haskell may be very helpful.

Haskell Crash Course

My goal now on the statically typed front is to become as proficient in Haskell as I can in a very short period of time. There seem to be plenty of resources available, but if you’re aware of any particularly helpful resources or tips, feel free to add a comment.

Tags:

Programming Language Popularity

April 21, 2009 in programming | 10 comments

Despite the numerous ways in existence to quantify programming language popularity, I thought I’d throw yet another one into the mix. I made a number of Google searches of the forms below and averaged the results:

"implemented in <language>"
"written in <language>"

I’m very curious to see how these stats change over time, so I’ve added a calendar item to recompute them in six months. Leave a comment if you’d like to add a programming language to the list, and I’ll update this article and it will be included in the recomputation six months from now.

Language # Results
C 1,905,500
Java 850,000
C++ 699,000
PHP 680,000
Python 396,000
Perl 365,500
C# 349,700
Lisp Family1 176,507
JavaScript 102,700
Ruby 99,650
Scheme 86,450
Lisp 61,900
Tcl 44,800
ML Family2 29,062
Haskell 22,550
Erlang 22,285
OCaml 22,000
Common Lisp 20,600
Prolog 17,750
Lua 13,065
Smalltalk 9,105
Arc 6,775
Forth 6,465
(S)ML3 5,173
Scala 3,570
Caml 1,889
Io 1,760
Clojure 782

1 combines Lisp, Scheme, Common Lisp, Arc & Clojure
2 combines OCaml, (S)ML, Caml
3 summed separate searches for sml and ml
Update 4/23/09 added C#, Tcl per comment requests.

Tags: , , , , , , , , , , , , , , , , , , , ,

Digest Tag Population in Ruby

March 1, 2009 in programming | 6 comments

I saw a post on comp.lang.lisp demonstrating the suitability of Common Lisp for functional programming. The poster asked to see versions in other languages including Ruby, so I thought I’d whip something up. Here’s the original post with description of the problem:

This one was too much fun for words in re how cool it is programming
with Lisp. I would like to see this in Ruby, Clojure, Qi, and
Scheme. The precise fun part tho is typing it all in in the final form
versus dividing the thing up into steps to get intermediate results,
ie, a test of one's mastery of one's language. Non-functional
languages I guess have no choice but to stop and assign temporaries.

Given:

(defparameter *pets*
  '((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
    (cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
    (snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
    (cow ((jersey 200)(heiffer 300)(moo 400)))))

Write:

(defun digest-tag-population (tag-population pick-tags count)...)

Such that:

(digest-tag-population *pets* '(dog cat snake) 5)

=> ((DOG CBRET 82) (DOG DOBER 42) (CAT RUSS 92) (CAT TIBET 52) (SNAKE
PYTHON 77))

...the rules being:

- consider only the populations of tags (the first symbol in each
sublist) found in the parameter pick-tags, a list

- take only the  most populous of the union of the populations

- return (tag name population) of the most populous in this order:

    firstly, by position of the tag in pick-tags
    second, ie within a tag, in descending order of population

(defun subseq-ex (st e s)
  (subseq s st (min e (length s))))

(defun digest-tag-population (tag-population pick-tags count)
  (flet ((tagpos (tag) (position tag pick-tags)))
    (stable-sort (subseq-ex 0 count
                   (sort (loop for (tag population) in tag-population
                             when (tagpos tag)
                             append (loop for pop in population
                                        collecting (list* tag pop)))
                     '> :key (lambda (x)
                               (caddr x))))
      '< :key (lambda (x) (tagpos (car x))))))

(defparameter *pets*
  '((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
    (cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
    (snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
    (cow ((jersey 200)(heiffer 300)(moo 400)))))

#+test
(digest-tag-population *pets* '(dog cat snake) 5)

And here is my Ruby version:

PETS = [
  [:dog, [[:blab, 12], [:glab, 17], [:cbret, 82], [:dober, 42], [:gshep, 25]]],
  [:cat, [[:pers, 22], [:siam, 7], [:tibet, 52], [:russ, 92], [:meow, 35]]],
  [:snake, [[:garter, 10], [:cobra, 37], [:python, 77], [:adder, 24], [:rattle, 40]]],
  [:cow, [[:jersey, 200], [:heiffer, 300], [:moo, 400]]]
]

def digest_tag_population tag_population, pick_tags, count
  tag_population.select {|e| pick_tags.include?(e[0]) }.
    inject([]) {|memo,obj| obj[1].each {|e| memo << [obj[0], e[0], e[1]] }; memo }.
    sort {|a,b| b[2] <=> a[2] }[0,count].
    sort_by {|e| [ tag_population.map{|p| p[0]}.rindex(e[0]), e[2] * -1] }
end

digest_tag_population(PETS, [:dog, :cat, :snake], 5)

Within the function:
Line 1: select elements that match the pick tags
Line 2: map to a list of tuples of the form [:dog, :blab, 12]
Line 3: sort the list of tuples by population and select the first count of them
Line 4: sort by tag position, population

Output:

[[:dog, :cbret, 82],
[:dog, :dober, 42],
[:cat, :russ, 92],
[:cat, :tibet, 52],
[:snake, :python, 77]]

I think Ruby compares very favorably. What do you think? Feel free to submit a version in another language.

Tags: , , , ,

« Older entries