lunes, febrero 08, 2010

Simple "shuffle" in Haskell

I got tired of Amarok so I've been using mplayer from the console. The only problem was to shuffle the playlists. Being a little bored I decided to write a simple shuffle script in Haskell.

module Main where

import Control.Applicative ((<$>))
import System.Random (getStdGen, randoms)
import Data.Ord (comparing)
import Data.List (sortBy)


main :: IO ()
main = do
ls <- lines <$> getContents
gen <- getStdGen
let rs = randoms gen :: [Double]
mapM_ (putStrLn . fst) . sortBy (comparing snd) $ zip ls rs



This approach is the easiest to implement but unfortunately it isn't "perfect". A functional "perfect shuffler" is discussed by Oleg here.

Now I can just write:

diegoeche@multivac:/Music$ find . -name *.mp3 | ./shuffle | \
mplayer -playlist -

jueves, agosto 20, 2009

The water is wet.

I've heard is a bad idea to start any post with "I'm sorry for not writing more often..." So I won't.

Were I live we usually say something like "he just discovered that the water is wet" when somebody makes a statement about something obvious. I'm just going to do exactly that.

I'm part of that unfortunate CS population that instead of receiving a wonderful introduction to programming with SICP had to deal with Java. Is really common to use Java for most of the courses that include projects. This semester I took this CG course so made the only choice I could. I chose to use Scala(1)

The good

I just translated the first simple Java3D example into Scala. And I mean, just plain translation of the code avoiding extra type annotations. Just not having to write all those types saves a lot of space! And I mean, this is what I'm talking about:

    val config = SimpleUniverse.getPreferredConfiguration();
val canvas3D = new Canvas3D(config);
this.add("Center", canvas3D);
val scene = createSceneGraph();
val simpleU = new SimpleUniverse(canvas3D);

Against:
    GraphicsConfiguration config = 
SimpleUniverse.getPreferredConfiguration();
Canvas3D canvas3D = new Canvas3D(config);
this.add("Center", canvas3D);
BranchGroup scene = createSceneGraph();
SimpleUniverse simpleU = new SimpleUniverse(canvas3D);
simpleU.getViewingPlatform().setNominalViewingTransform();

I mean... this really counts if you think about not wasting columns as I do.

The bad

If you write something like:
    def createSceneGraph() = {
val objRoot = new BranchGroup();
objRoot.addChild(new ColorCube(.4));
objRoot;
}


But let's say you didn't write the "=", or made explicit the return type, or wrote the "return" keyword, or wrote it without curly braces. Or just make combinations of those.

In the best case you get a compiling error.
Sometimes it makes exactly what you want.
Sometimes it compiles... But with different semantics!

I would really prefer a concise way to write it and no alternatives. An F# kind-of light-syntax would be really nice.

(1): I could've used Groovy, Clojure or [write your jvm-based language here] too, but I prefer static typing.

viernes, noviembre 21, 2008

Poor man's code folding for F#

Code folding is one of those "features" that I practically never use. The reason is that in some tools the feature doesn't play well with the incremental search. More important is that there's some kind of people that think that a 3000 thousand lines file folded into methods, properties and constants is "nicer". (Trust me they exist)

Some days ago I got some kind of Emacs-fever thanks to the Emacs wiki. I set-up the jabber client, fixed that nasty behaviour with the clipboard and discovered the outline-minor-mode.

The outline-minor-mode is basically a mode for hierarchical text folding. I'm not going to spend my time giving an explanation having this

The mechanism behind this mode is so simple but yet so powerful. Is just a regex.. The hierarchy of the folding depends on the size of the regex match.

Let's imagine this simple example:
module Search =

type IQueue<'c,'a> =
{ makeQueue: 'a list -> 'c
empty: 'c -> bool
first: 'c -> 'a
removeFirst: 'c -> ('a * 'c)
insertAll: ('a list * 'c) -> 'c
}


Using something as simple as this:
(setq outline-regexp " *\\(let ..\\|type .\\|module\\)")

We are able to fold the code in different ways:
module Search =

type IQueue...
module Search... 

But also... We can fold every let definition!
For example:
    let treeSearch<'c,'a> 
(succesors: 'a -> 'a list)
(queue: IQueue<'c,'a>)
(goal: 'a -> bool)
(i0: 'a ) =
let rec explore (fringe: 'c) =
if queue.empty fringe then
failwith "Not Found"
else
let (first, fringe) = queue.removeFirst fringe
if goal first then
first
else explore (queue.insertAll (succesors first, fringe))
explore (queue.makeQueue [i0])

Can fold into this:
    let treeSearch<'c,'a> 
(succesors: 'a -> 'a list)
(queue: IQueue<'c,'a>)
(goal: 'a -> bool)
(i0: 'a ) =
let ...
explore (queue.makeQueue [i0])

The best thing is that it plays perfectly good with C-s and C-y. The regex can be extended to manage any computation expression builder, if-then-else, while, for, match-with blocks.

If you want too hook it to the F# mode...
(setq inferior-fsharp-program "~/lib/fsharp/fsi.sh")
(setq fsharp-compiler "~/lib/fsharp/fsc.sh")
(add-hook 'fsharp-mode-hook
(lambda () (outline-minor-mode)
(setq outline-regexp " *\\(let ..\\|type .\\|module\\)")))

martes, noviembre 11, 2008

Copy to Html

I was going to write something completely different but I had some troubles copying the source code to my blog. I Usually use a little script from Steve Yegge for copying the highlighted text from Emacs to Html.

It had some strange trouble converting the RGB colors and it was not setting the values of the default font.

Here is the code: (using the highlighter :D)

(defun html-string-color (face key)
(mapconcat (lambda (x) (format "%.2x" (/ x 256)))
( color-values (face-attribute
(make-face face) key)) ""))

(defun syntax-highlight-region (start end)
"Adds <font> tags into the region that correspond to the
current color of the text. Throws the result into a temp
buffer, so you don't dork the original."

(interactive "r")
(let ((text (buffer-substring start end)))
(with-output-to-temp-buffer "*html-syntax*"
(set-buffer standard-output)
(insert (format "<div style=\"color:#%s; background:#%s\" ><pre>"
(html-string-color 'default :foreground)
(html-string-color 'default :background)))
(save-excursion (insert text))
(save-excursion (syntax-html-escape-text))
(while (not (eobp))
(let ((plist (text-properties-at (point)))
(next-change
(or (next-single-property-change
(point) 'face (current-buffer))
(point-max))))
(syntax-add-font-tags (point) next-change)
(goto-char next-change)))
(insert "\n</pre></div>"))))

(defun syntax-add-font-tags (start end)
"Puts <font> tag around text between START and END."
(let (face color rgb name r g b)
(and
(setq face (get-text-property start 'face))
(or (if (listp face) (setq face (car face))) t)
(setq color (face-attribute face :foreground))
(setq rgb (assoc (downcase color) color-name-rgb-alist))
(destructuring-bind (name r g b) rgb
(let ((text (buffer-substring-no-properties start end)))
(delete-region start end)
(insert (format "<font color=#%.2x%.2x%.2x>"
(/ r 256) (/ g 256) (/ b 256)))
(insert text)
(insert "</font>"))))))

(defun syntax-html-escape-text ()
"HTML-escapes all the text in the current buffer,
starting at (point)."

(save-excursion (replace-string "<" "<"))
(save-excursion (replace-string ">" ">")))


BTW there's some minor issue with the greater than symbol inside of the strings.

Change in the language... For good?

After thinking about it carefully I have decided to start writing my "Programming" blog in English. I don't think I'm going to lose any of the current readers (Is there any reader out there???) but instead, this can be the perfect exercise for improving my horrible English.

It would be really nice if you can point out any nasty grammatical mistake or misuse in the words (I have a really a bad time with some phrasal verbs)

viernes, octubre 17, 2008

Números Normales

Últimamente ando pensando en números normales.

Cojamos 2:

El número de Champernowne:
0.123456789101112131415...
La constante de Chaitin
0.00787499699...

Dicen que Pi es normal... Si Pi es normal quiere decir que 1, 12, 123, 1234, 12345, 123456 están contenidos en Pi.

Si pi es normal 0, 007, 00787499699 están contenidos en pi.

Si tomamos un numero de tamaño n arbitrario substring de Champernowne o la constante de Chaitin estará contenido en pi... Y algo que podemos estar seguros es que independiente de si pi es normal o no cualquier substring estará presente en el de Champernowne.

Podemos adentrarnos infinitamente en los substrings de Champertown que contienen substrings de la constante de Chaitin... cadenas sin nombre, cadenas con nombres, fragmentos de pi, pi/2, pi/4...

martes, octubre 14, 2008

Reader Monad en F#

Intro

El proyecto en el que trabajo usa en forma extensiva Linq para realizar todas las operaciones con la base de datos.

Éste es un ejemplo clásico de consulta:(1)


  112 let findById (db: MyProjectClassesDataContext, id) =

  113     SQL <@ {    for c in %db.Products

  114                 when c.ProductID = %id

  115                 -> c } @> |> Seq.hd



El ejemplo compila la expresión a un query nativo de SQL y lo ejecuta. El objeto por el cual nos "comunicamos" con la base de datos es el "DataContext" (En este caso le pusimos un nombre super enterprisey "MyProjectClassesDataContext" para darnos de importantes).

"DataContext" También nos ayuda a realizar cambios en forma transaccional. Por ejemplo:

  117 let changeDescription id text =

  118     let db = new MyProjectClassesDataContext()

  119     let product = findById(db,id)

  120     product.Description <- text

  121     db.SubmitChanges()



Cambia la descripción en forma transaccional.

Si tuviésemos ésta otra definición:


  123 let changeToLiquors id =

  124     let db = new MyProjectClassesDataContext()

  125     let product = findById(db,id)

  126     product.Type <- "Liquors"

  127     db.SubmitChanges()

  128 

  129 let changeDescriptionAndToLiquors id text =

  130     changeDescription id text

  131     changeToLiquors id



La creación de 2 SubmitChanges hace que hallan realmente 2 "transacciones" una puede realizarse con éxito pero la otra puede fallar. En algunos casos esto representa un peligro para la integridad de la base de datos. La forma correcta si queremos atomicidad en la operación sería crear un solo SubmitChanges para ambas operaciones.

Así mismo, los objetos de un DataContext, no pueden ser compartidos entre diferentes DataContext. Si digamos tengo los DataContext A y B, saco un producto de A y hago B.SubmitChanges(); el producto dado que pertenece a A, no es persistido en la base de datos.

Ésto nos obliga a tener un solo DataContext por transacción.

  117 et changeDescription db id text =

  118     let product = findById(db,id)

  119     product.Description <- text

  120 

  121 let changeToLiquors db id =

  122     let product = findById(db,id)

  123     product.Type <- "Liquors"

  124 

  125 let changeDescriptionAndToLiquors db id text =

  126     changeDescription db id text

  127     changeToLiquors db id



Incluso la última función la construimos recibiendo el DataContext como parámetro. Si estamos construyendo una librería ¿Quién somos para decir cuando queremos hacer persistencia? cada SubmitChanges e instanciación de DataContext es un problema si queremos componer después cada una de las funciones.

Pero ahora nos toca pasar SIEMPRE el DataContext, muchas veces toca hacer "types annotations". Y aceptemoslo... escribo a duras penas a 20 WPM. Y los nombres enterprisey no ayudan. A veces con aplicación parcial puede uno lograr ciertos ahorros pero está lejos de ser una solución.

Y bien?

Computations which read values from a shared environment.

Kurva jó!

F# posee azúcar sintáctica parecida a la sintaxis "do" de Haskell.

Definimos la monada(2)


   11 module Reader =

   12     type Reader<'e,'a> = Reader of ('e -> 'a)

   13     let apply (Reader f) r = f r

   14     let returnM x = Reader (fun e -> x)

   15     let bindM m f =

   16         Reader (fun e -> apply (f (apply m e)) e)

   17     let letM v f = bindM (returnM v) f

   18     let delayM f = bindM (returnM ()) f

   19 

   20     (*Reader Monad*)

   21     type MReaderBuilder() =

   22         member b.Return(x) = returnM x

   23         member b.Bind(v,f) = bindM v f

   24         member b.Delay(f) = delayM f

   25         member b.Let(v,f) = letM v f

   26 

   27     let reader = new MReaderBuilder()

   28     let ask = Reader (fun e -> e)

   29     let local f c = Reader (fun e -> apply c (f e))

   30     let asks sel = bindM (ask) (returnM << sel)

   31 



Internamente la monada no es mas que una función desde el "Entorno" hacia un "Retorno". Empecemos con ejemplos sencillos de como usar la monada.

Usando un string como contexto.


   35 let lengthOfString =

   36     reader {let! length = asks String.length 

   37             return length

   38            }



Simplifiquemos el contexto a un simple string. Esta definición nos retorna dado un contexto particular la longitud del mismo.

Para pasar el contexto:


   40 apply lengthOfString "hello"



(Si... retorna 4)

Ahora... A diferencia de Haskell, F# permite Side Effects. De esta manera lo siguiente también es posible(3).


   42 let lengthOfModifiedString =

   43     reader {let! length = lengthOfString

   44             let! lengthModified =

   45                 local

   46                     ((+) "Preffix") lengthOfString

   47             let! env = ask

   48             do printfn "%A" env

   49             return sprintf "%d: %d: %s"

   50                    length lengthModified env

   51            }



"asks" aplica la función al contexto.
"local" crea un contexto modificado(4) mediante una función.
"ask" retorna el contexto o entorno.

De la misma manera podemos usar el reader en casos mas complejos.


  103 type DBReader<'a> =

  104     Reader<MyProjectClassesDataContext, 'a>

  105 

  106 let getClients (db:MyProjectClassesDataContext) =

  107     db.Clients

  108 let getProducts (db:MyProjectClassesDataContext) =

  109     db.Products

  110 let getClientProducts (db:MyProjectClassesDataContext) =

  111     db.ClientsProducts

  112 

  113 let getClientByName1 name : DBReader<Person> =

  114     reader {let! clients = asks getClients 

  115             return List.find (fun (x) -> x.Name = name) clients

  116     }



Él código(5)

(1) Si mal no estoy la forma de realizar este tipo de consultas cambio con el CTP de F#

(2) Él nombre que se le da en F# son "computation expressions"

(3) El "do" para las expresiones que retornan unit creo que ya no es necesario con la última versión de F# (CTP Release).

(4) Toca recordar que estos es útil tratando con estructuras inmutables (i.e string).

(5) No usa la ultima versión de F#

miércoles, octubre 08, 2008

Orgullo universitario

Misión

"La Universidad EAFIT tiene la Misión de contribuir al progreso social, económico, científico y cultural del país, mediante el desarrollo de programas de pregrado y de postgrado -en un ambiente de pluralismo ideológico y de excelencia académica- para la formación de personas competentes internacionalmente; y con la realización de procesos de investigación científica y aplicada, en interacción permanente con los sectores empresarial, gubernamental y académico."


En letras pequeñas... Pluralismo ideológico incluye pero no está limitado a: descuentos en teléfonos móviles, tarjetas de crédito y tiquetes aéreos.