Need help translating Lisp code into C#

Discussion of Common Lisp

Need help translating Lisp code into C#

Postby klactose » Sat Nov 28, 2009 1:39 pm

Hello all,

This is my first post, hopefully it's in the correct place. I am in the process of translating a program from Common Lisp into C#, most of it has gone smoothly but I have run across two blocks of code that are giving me a bit of trouble. The two functions I am having difficultly are the first two I list below. I am including the the last function, COUNT-THEM, because it is being used in the first function. If anyone can help me translate these two pieces of code into C#, or even simply translate them into pseudo code that I can understand (then I can translate it into C# myself), I'd be very grateful.

Thanks in advance for any assistance you all can provide!


The COUNT-HIGHEST function:
Code: Select all
(defun COUNT-HIGHEST (lists)
  "Returns the highest occuring pattern in its arg."
  (let* ((sorted-numbers (my-sort #'< (mapcar #'second lists)))
         (numbers-only (remove-duplicates sorted-numbers))
         (counts (count-them numbers-only sorted-numbers)))
    (find-all (nth (position (first (my-sort #'> counts)) counts) numbers-only)  lists)))


The MY-SORT function:
Code: Select all
(defun MY-SORT (function lists)
  "Non-destructive sort function."
  (loop for item in (sort (loop for array-2 in lists
                                collect (list array-2))  function :key #'car)
        collect (first item)))


The COUNT-THEM function:
Code: Select all
(defun COUNT-THEM (singles numbers)
  "Returns the counts of its first arg in its second arg."
  (if (null singles)()
      (cons (count (first singles) numbers)
            (count-them (rest singles) numbers))))


FYI:
array-2 referenced in above is initially defined as:
Code: Select all
(defVar ARRAY-2 (make-array (list 5)))


Also, if anyone is curious, these pieces of code come from a program called "Network" written by David Cope. The full program along with others can be found here. Unfortunately all of his files are archived in .sit format, so you'll need StuffIt Expander to open them.
klactose
 
Posts: 2
Joined: Sat Nov 28, 2009 12:49 pm

Re: Need help translating Lisp code into C#

Postby Harleqin » Tue Dec 01, 2009 6:38 am

I don't know C# enough to tell you how to implement this, but I'll try to explain
what these functions do. I believe that you would use different data structures
in C# (and in modern Common Lisp, too, actually).

klactose wrote:
Code: Select all
(defun COUNT-HIGHEST (lists)
  "Returns the highest occuring pattern in its arg."
  (let* ((sorted-numbers (my-sort #'< (mapcar #'second lists)))
         (numbers-only (remove-duplicates sorted-numbers))
         (counts (count-them numbers-only sorted-numbers)))
    (find-all (nth (position (first (my-sort #'> counts)) counts) numbers-only)  lists)))



This takes a list of lists. The second item of each of these lists is
supposed to be a number. The function then finds the number with the
highest count and returns a list of all those lists that have this
number as second item (I presume, because I don't know how FIND-ALL is
defined).

Example:

Code: Select all
(count-highest '((A 2 B) (C 3 D) (E 5 F) (G 3 H)))
=> ((C 3 D) (G 3 H))


If we assume that FIND-ALL is defined like this (which is a bit bad
because a more general behaviour would usually be expected from a
function named like this):

Code: Select all
(defun find-all (number lists)
  "Returns all lists in lists that have number as second element"
  (remove number lists :test-not #'= :key #'second))


COUNT-HIGHEST could be defined much more efficiently like this:

Code: Select all
(defun count-highest (lists)
  "Returns a list of those lists in lists that have the number with the highest
count as second element."
  (let ((counts (make-hash-table)))
    (flet ((count-up (number)
             (if (gethash number counts)
                 (incf (gethash number counts))
                 (setf (gethash number counts) 1))))
      (dolist (l lists)
        (count-up (second l)))
      (let ((highest-count (loop with max-count = 0
                              for c being the hash-keys of counts
                              do (when (> (gethash c counts) max-count)
                                   (setf max-count c))
                              finally (return max-count))))
        (find-all highest-count lists)))))


I believe that this is also more readily understood. I am using a hashtable for keeping the counts, because I don't know the range of numbers to expect. If that range is not too large and known, the hashtable could be replaced by an array.

Code: Select all
(defun MY-SORT (function lists)
  "Non-destructive sort function."
  (loop for item in (sort (loop for array-2 in lists
                                collect (list array-2)) function :key #'car)
        collect (first item)))



This takes a function to sort by (e.g. #'<) and a list of lists. It
then wraps each member of that list of lists into another list, sorts
them by the original members, and finally unwraps them into the result
list. What
array-2 is outside of the loop is totally irrelevant,
because the "for" inside the loop establishes a local binding. The
use of the name
array-2 in this context might be a code smell.
Anyway, this could have been achieved in a simpler and more
obviously correct form like this:

Code: Select all
(defun my-sort (function lists)
  "Non-destructive sort function."
  (sort (copy-list lists) function))


Code: Select all
(defun COUNT-THEM (singles numbers)
  "Returns the counts of its first arg in its second arg."
  (if (null singles)()
      (cons (count (first singles) numbers)
            (count-them (rest singles) numbers))))



This takes two lists and returns a list of counts, which are the
individual counts of each element from the first list in the second.
Example:

Code: Select all
(count-them '(a b c) '(a b c a c a b))
=> (3 2 2)
;; there are 3 a, 2 b, and 2 c in the second list


This function could be made tail-recursive (if recursion is desired),
but it would usually be implemented simpler like this:

Code: Select all
(defun count-them (singles numbers)
  (mapcar (lambda (s)
            (count s numbers))
          singles))
"Just throw more hardware at it" is the root of all evil.
Svante
Harleqin
 
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Need help translating Lisp code into C#

Postby klactose » Tue Dec 01, 2009 7:00 pm

Hello Harlequin and thank you SO much for responding. It will take me some time to pour over your response because I am not well versed in Lisp, but this has helped a lot already!

Also, here is the original FIND-ALL function, I am sorry I didn't include it in the original post (I thought that it was one of Lisp's built in functions).

Code: Select all
(defun FIND-ALL (number lists)
  "Returns all of the patterns associated by cdr with number."
  (cond ((null lists)())
        ((equal (second (first lists)) number)
         (cons (first lists)
               (find-all number (rest lists))))
        (t (find-all number (rest lists)))))


I think I understand what this function does. It is a recursive function that takes a number and a list of lists and returns a list of lists. The list it returns will include all the lists that have their second value equal to the number passed as a parameter. Which would be exactly what you presumed, but in a more verbose way then you provided.

Thanks again!
klactose
 
Posts: 2
Joined: Sat Nov 28, 2009 12:49 pm


Return to Common Lisp

Who is online

Users browsing this forum: Bing [Bot] and 1 guest