Programación funcional (Scala, Clojure, etc.)

#122 los paréntesis hacen falta porque en Clojure la unidad básica de ejcución en la S-expresión y no los statements como en el resto de lenguajes. No son opcionales, sino que denotan:

(funcion arg1 arg2 ... argN)

En este caso, fn en sí misma es una función (que devuelve a su vez una función) por lo que necesitas "wrappearla" en paréntesis para que se ejecute y devuelva la función que defines (luego vuelvo a este concepto.)

4clojure funciona de una forma especial. Como ya habrás visto, comprueba si tu respuesta es correcta con varios casos de prueba. En el problema 19 en concreto el primer caso de prueba es:

(= (__ [1 2 3 4 5]) 5)

Lo que tú introduces se sustituye por __. Quedaría:

code) (ret (rest x )) (first x)) [1 2 3 4 5]) 5)[/code]
Igual aquí es donde estaba tu confusión. Lo que hace (fn ...) es crear una función y devolverla. Es un concepto importante: no estás definiendo la función ret(x) sino que simplemente la estás creando. Fíjate que queda...

((fn ...) [1 2 3 4 5])

...es decir, aplicar la función al argumento [1 2 3 4 5].

Sin paréntesis como ves [1 2 3 4 5] no queda fuera de la creación de la función sino dentro de esta. No sería un argumento de la función que vas a ejecutar, sino de la función fn que usas para crear tu función.

Haciendo (fuera de 4clojure) algo como...

(defn ret [x]
  (if (not (empty? (rest x)))
      (ret (rest x))
      (first x))

(ret [1 2 3 4 5])

...obtienes el mismo resultado. Fíjate que defn no sólo crea una función sino que también la define. El nombre queda disponible globalmente. (defn ...) no es más que un shorthand para (def nombre (fn ...)).

No sé si me he explicado bien. La clave es entender lo de que fn es una función que devuelve funciones. El resultado de (fn ...) es un objeto función que es el que aplicas sobre los argumentos posteriormente.

Insisto de nuevo, la imagen de fn es una función en sí misma, la que aplicas posteriormente sobre los argumentos. Y para explicarlo de otra forma (creo que ya van como 5 veces que va lo mismo de distinta forma, espero que no quede duda xD)

fn(nombre, argumentos, cuerpo) -> cuerpo(*argumentos) donde * denota "slicear" el array de argumentos. fn por tanto devuelve la función que define el cuerpo.

Tú hacías...

fn(ret, [x], cuerpo, [1 2 3 4 5])

...mientras que querías hacer...

fn(ret, [x], cuerpo)([1 2 3 4 5])

...o para más claridad añadimos paréntesis...

(fn(ret, [x], cuerpo))([1 2 3 4 5])

Redistribuye los paréntesis para que tengan aspecto de S-expresión y verás que tiene sentido.

Trivia: si fn no define el nombre (de hecho la función que devuelve fn es anónima, no tiene un nombre asociado), ¿para qué pasárselo entonces? De hecho es opcional, pero... ¿por qué lo admite siquiera?

En este caso es necesario porque la función se refiere a sí misma (recursiva) y aunque esta sea anónima "cara al público" sí que necesitas una forma de nombrarla interna (es decir, el nombre no queda asociado en el espacio de nombre global, pero si en el espacio de nombre local del cuerpo de la función).

Si la función no fuera recursiva podrías omitir el nombre.

PD: ¡me alegro de que te hayas puesto con Clojure! Te va a encantar y como matemático lo vas a ver bastante lógico (a un programador le cuesta más ver eso de que las funciones puedan devolver funciones y demás).

#124

1. Sí, lo has puesto bien y son equivalentes (Trivia: %1 de hecho lo puedes dejar como % a secas).

2. Pfff, has dado duro en el hueso de Clojure xD

'(a b c d) o (list a b c d) es una lista simplemente-enlazada. Conceptualmente la puedes entender como:

• El elemento d concatenado (cons, en realidad) a la lista vacía '() = '(d)
• El elemento c concatenado a la lista '(d) = '(c (d)) = '(c d) (ojo, los paréntesis de la segunda forma son sólo por claridad, si lo escribe así el Clojure forma otra cosa, una lista dentro de la lista).
• El elemento b concatenado a la lista '(c d) = '(b c d)
• El elemento a concatenado a la lista '(b c d) = '(a b c d)

Es decir, la lista es algo como cmd)[/cmd].

¿Qué implica esto? Las únicas operaciones "naturales" sobre la lista son:

• (first lista) -> toma el primer elemento (la cabeza) de la lista.
• (cons elemento lista) -> añade elemento a la cabeza de lista (lo que hemos hecho en las operaciones para construirla uno por uno).
• (rest lista) -> toma la cola de la lista, es decir, deshace el último cons sobre esta.

Contar una lista por ejemplo no es una operación natural. La única forma de contar una lista es hacer (rest ...) recursivamente hasta que encuentras ' () y el número de iteraciones que has dado es la longitud de esta.

En efecto además de eso las listas son secuencias... pero ojo, una secuencia en Clojure no es más que un "contrato" (o interfaz). Cuando una estructura de datos es una secuencia significa que se pueden realizar las operaciones que comentaba antes que soporta la lista. Se podría decir que una lista es la estructura de datos más simple que implementa la interfaz "secuencia".

Hay otras estructuras de datos que también son secuencias, por ejemplo las listas infinitas (o lazy lists, que ya verás en profundidad en 4clojure creo). No son listas (es imposible tener una lista infinita técnicamente) sino un algoritmo que define dado un elemento su siguiente (y de ahí se deriva la lista), pero tienen el mismo interfaz con first, next, etc.

Es importante distinguir entre estructura e interfaces. La estructura es cómo se organiza internamente, mientras que las interfaces es cómo se puede acceder a estos datos. Una misma estructura puede tener varios interfaces.

Como bien dices [a b c d] es un vector y se diferencia de la lista tanto en su estructura interna (un árbol 32-ario creo) como en el contrato o interfaz (IPersistentVector). La interfaz del vector permite acceder a los elementos por índice, añadir al final del vector, y lo más importante: es una estructura contada. Hacer (count mi-vector) es prácticamente gratis (es un valor guardo en la propia estructura).

Es difícil ver la separación entre estructura e interfaz porque muchas veces van ligadas (no tiene sentido una lista indexada), pero lo verás mejor con los sets.

#{a b c d} sería un conjunto (un hash set). La estructura de datos interna es una tabla hash que relaciona cada elemento consigo mismo. Si al acceder a un elemento (calcula el hash y busca en la tabla) lo encuentra, pues el elemento está en el conjunto. Como operaciones naturales tienes adición y eliminación y las típicas de conjuntos: conjunción, disyunción, intersección....

Con el mismo interfaz pero un pequeño detalle, tenemos los sorted-sets de la forma (sorted-set ...). La estructura detrás no es una tabla hash sino un vector, por lo que el conjunto está ordenado (y por tanto implementa una interfaz para acceder a sus elementos de forma ordenada aparte de la interfaz normal de los sets).

Cuidado, sin la almohadilla # las llaves {} no son un set, sino un mapa (te confundiste). Un mapa es una función que relaciona cada elemento impar con su correspondiente par: {:a 1 :b 2}, dado :a devuelve 1. Como los vectores, son funciones de sí mismos (aunque no necesariamente, esto también es sugar tanto en vectores como aquí, hay alternativas en forma de función). Como estructura detrás tienen una tabla hash pero no se relacionan a sí mismos como el hash-set, sino que relacionan cada elemento con su valor asociado. Como operaciones naturales: añadir, quitar y acceder.

Lo de que haya la notación de ' (), #{}, [], etc. no es más que por conveniencia. Todas tienen alternativa: (list ...), (hash-set ...), (vector ...) y no son más que "azúcar sintáctico".

"y que la función count es O(1) en secuencias (creo) pero no en vectores (creo)"

Como comento antes, al revés.

"porque puedo escribir: = [a b c d] ' (a b c d)"

Supongo que te refieres a (= [a b c d] '(a b c d)) (ojo con los paréntesis, ¡es una S-expresión y son necesarios!).

En efecto, puedes hacerlo y el resultado es true. La cuestión es que la función = usa por detrás nada más y nada menos que la interfaz secuencia:

• Si (not= (first a) (first b)) -> devuelve false
• Else (recursion (rest a) (rest b))

Los vectores si no me equivoco también implementan esta interfaz secuencia (puedes hacer (rest ...) a un vector) aunque no son muy buenos en ello: tienen que construir el vector resultado completo (en realidad usan truquitos para optimizar, pero nada como una lista pura para hacer (rest ...)) Del mismo modo, a una lista puedes hacerle (nth ...) aunque será lenta de cojones (en concreto O(N), tiene que hacer N-1 rests + 1 first).

Por otro lado las estructuras las puedes "castear". (vec '(1 2 3 4)) devuelve un vector, (seq [1 2 3 4]) devuelve una secuencia (pero esto obviamente es lento de cojones, tiene que hacer las estructuras desde cero).

No he entrado en cuales son más eficientes ni nada de eso por no liarme, pero vamos, la información está por la internet. Aún así mientras que entiendas cuáles son sus operaciones naturales te da un poco igual la eficiencia: las naturales son más eficientes por razones obvias.

De momento ni te preocupes por esta mierda, ya lo aprenderás con el lenguaje. Con que te quedes con el big-picture que te acabo de hacer, todo ok.

Aquí más en profundidad: http://clojure.org/data_structures

Referencias necesarias: la página oficial (MUCHA info, de lo mejorcito para entender el core del lenguaje), la guía rápida de referencia (la lista con las funciones más usadas) y clojuredocs. Creo que están todos en #1.

TRIVIA: para las listas hay que hacer ' (1 2 3 4...) con la comilla simple. ¿Por qué no (1 2 3 4) a secas?

Las S-expresiones también son listas (Lisp es homoicónico, datos y código son lo mismo). La única diferencia es que cuando estás programando se asume que el primer elemento de la lista es la función que se aplicará sobre los argumentos. La comilla le dice al Reader de Clojure que la lista que viene despues no hay que ejecutarla, que es una lista y punto.

EDIT: ¡IMPORTANTE! Casi se me olvida. Clojure te permite "interactuar" con las estructuras para ver sus características. P.ej. (seq? ...) te dice si una función es una secuencia.

Curiosamente (seq? [1 2 3 4]) = false (tiene sentido, un vector no es una secuencia) pero sin embargo, tal y como te comentaba: (sequential? [1 2 3 4]) = true (un vector tiene, entre otras una interfaz Sequential).

También puedes usar (class? ...) para ver la estructura concreta con la que te encuentras (que no sus interfaces).