Wednesday, September 30, 2009

Hyperspec treasure: pathname-match-p

There was a great post at pozorvlak about Slava's(*) Haskell challenge. For the lazy here's a little copy paste:

This piece of code goes through a parse tree of Haskell source code, locates every reference to an identifier that ends with "Widget", puts it on a list, and removes duplicates so every identifier is represented in the list only once.


extractWidgets :: (Data a) => a -> [String]
extractWidgets =
nub . map (\(HsIdent a)->a) . listify isWidget
where isWidget (HsIdent actionName)
| "Widget" `isSuffixOf` actionName = True
isWidget _ = False


Steven Apter's q solution was impressive:

a:distinct raze over x
a where a like "*Widget"


So I tried to reproduce it in lisp. Distinct is remove-duplicates, raze is our good friend flatten, but I lacked like. Being lazy I've asked the denizens at c.l.l.(**) for a freebie and they were more then helpful providing plenty of alternatives. Below is Vassil Nikolov solution:

;;; Vassil Nikolov
(defun widgets (tree)
(flet ((widgetp (n &aux (c= #'char-equal))
(zerop (or (mismatch "widget" (string n)
:from-end t :test c=) 0))))
(remove-duplicates
(remove-if-not #'widgetp (flatten tree)))))

Four lines isn't that bad(***) but I still disliked the flat part. Then Dmitriy Ivanov saved the day suggesting pathname-match-p.

(defun like-widget (l)
(remove-duplicates
(remove-if-not
(lambda (x)
(pathname-match-p (string x) "*Widget"))
(flatten l))))

Clarity improved drastically. Afterwards it was easy, using my golf library and extracting like as general purpose utility I've decreased it into two clear lines.

(defun like (x p)
(apply #'pathname-match-p
(mapcar #'string (list x p))))

(defun widgets (l)
(unique (keep (f like x "*Widget") (flatten l))))


Same number of tokens (11) with Steven Apter solution, but mine having extra parens. The author claims that Lisp is longer and messier than Haskell for easy problems which I disagree with. By programming the programmable language lisper could quickly achieve extreme terseness, or continue to write very long and descriptive names and be faithful to the tradition. But the choice is there, always.

(*)
The author of two great lisp libraries:cl-cont & weblocks
(**)
Thanks to:Pascal J. Bourguignon, Thomas A. Russ, Mirko Vukovic, Stanislaw Halik and Vassil Nikolov
(***)
Due to blogger lousy code formatting some solutions are split to several lines.

3 comments:

  1. Sweet. I hadn't thought of pathname-match-p that way before.

    ReplyDelete
  2. Every function is made to be used and abused in different ways.

    ReplyDelete
  3. Sounds like pathname-match-p needs a better name to me.

    ReplyDelete

Note: Only a member of this blog may post a comment.