Es difícil encontrar pequeños ejemplos que sean inequívocamente mejores en Haskell. Incluso si tenemos un programa más limpio y corto en Haskell, las personas que no estén familiarizadas con sus abstracciones afirmarán que la versión de Python es “obvia” y que la versión de Haskell es demasiado esotérica. Y oye, supongo que eso es cierto para ellos, solo dice más sobre lo que están familiarizados que la calidad del código en cualquier idioma.
Siento que esto descalifica a la mayoría de las frases de Haskell: demasiadas personas las verían como simplistas y poco más. Considere la función “list powerset” citada con frecuencia que le ofrece todas las sublistas del argumento:
powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])
- ¿Qué es un algoritmo? ¿Es simplemente una máquina de Turing? Si no, ¿qué es?
- ¿Por qué no puede haber un algoritmo de clasificación que tenga el mejor y el peor caso de N tiempo de ejecución (por ejemplo, lineal)?
- ¿Por qué usamos algoritmos genéticos?
- ¿Qué software / algoritmo se usa para hacer partidos de la liga de fútbol o cualquier evento deportivo enorme?
- ¿Dónde y cómo puedo aprender sobre la creación / comprensión de algoritmos de negociación de acciones?
Personalmente, estoy completamente cómodo con este código. Define qué es un conjunto de potencia: es lo que obtienes si ambos incluyes y excluyes todos los elementos posibles en una lista. Pero ya me siento cómodo pensando de esta manera; alguien que no esté, tal vez alguien que no esté familiarizado con el funcionamiento de la mónada de la lista o alguien con una mentalidad más operativa, encontraría esta función ofuscada. (De hecho, ese es exactamente el segundo comentario dicho en el hilo de Reddit que encontré buscando en Google “Haskell powerset”).
El código es demasiado lindo.
Un buen ejemplo tendría que ser un poco más grande y depender de la expresividad de Haskell de formas que serían incómodas de reproducir en Python. Entonces, eso es lo que tenemos que identificar primero: de qué manera es Haskell más expresivo, ya sea como lenguaje o mediante bibliotecas, de lo que vería en Python.
Tengo un par en mente, pero podríamos llegar a más.
- Los tipos de datos algebraicos , junto con la coincidencia de patrones, facilitan el trabajo con toda una clase de tareas. En particular, es mucho más fácil escribir código que funcione con lenguajes de programación o lenguajes formales.
- La pereza es excepcionalmente poderosa. Entre otras cosas, facilita la representación de datos de tamaño y resolución arbitrarios sin perder información cuando las cosas se combinan, “en la costura”. Un ejemplo un poco complicado es un tipo de datos para datos de imágenes en 2D con una extensión y resolución infinitas , que podemos obtener con cuadrantes perezosos.
El segundo es especialmente relevante: me imagino haciéndolo en Haskell, incluso razonablemente fácilmente en el caso más simple, y no puedo imaginarme hacerlo en Python. En el mejor de los casos, trataría de transferir mi código Haskell, pero sería increíblemente tedioso y propenso a errores.
Tipos de datos algebraicos
En Haskell, es natural expresar sus cálculos mediante la coincidencia de patrones sobre tipos de datos algebraicos. A menudo, el código que tiene que escribir fluye directamente de los tipos: configura su problema y la solución queda directamente fuera de la configuración.
De hecho, esto apareció en el mundo real, en mi entrevista con Jane Street. Por supuesto, no puedo decirte los detalles de la pregunta, pero me fue mucho más fácil de lo que debería. Fue significativamente más fácil que las otras preguntas que tenía y creo que lo hice mucho mejor que la mayoría de las personas, todo porque usé Haskell. (Bueno, para ser justos, OCaml habría sido igual de bueno en ese caso).
¿Y por qué? Porque se centró en trabajar con lenguajes formales y, a través de eso, árboles. Después de definir los tipos que necesitaba, la resolución del problema fue casi sistemática: el patrón coincidía con mis tipos, manejaba todos los casos y derivaba la función final paso a paso.
Esto será válido para la mayoría de los problemas relacionados con lenguajes de programación o lenguajes formales, especialmente problemas lo suficientemente pequeños como para caber en una entrevista. Un ejemplo podría ser implementar un solucionador algebraico que pueda manejar variables y simplifique las expresiones aritméticas tanto como sea posible. Empiezas con los tipos
data Expr = Var String
| Lit Integer
| Expr :+: Expr
| Expr :-: Expr
| Expr :*: Expr deriving (Show, Eq)
Luego implementas la lógica para simplificar. Es un poco complicado, pero fluye directamente de los tipos, lo suficientemente simple en Haskell pero, creo, bastante más difícil en Python.
simplify :: Expr -> Expr
simplify expr
| nextStep == expr = expr
| otherwise = simplify nextStep
where nextStep = case expr of
Var x -> Var x
Lit n -> Lit n
(Encendido n1: +: Encendido n2) -> Encendido (n1 + n2)
(Encendido n1: -: Encendido n2) -> Encendido (n1 – n2)
(Encendido n1: *: Encendido n2) -> Encendido (n1 * n2)
(e1: +: e2) -> simplificar e1: +: simplificar e2
(e1: -: e2) -> simplificar e1: -: simplificar e2
(e1: *: e2) -> simplificar e1: *: simplificar e2
Una parte realmente genial es que este código es fácil de extender. Por ejemplo, para manejar 0 y 1 inteligente, solo tendría que agregar algunos patrones más:
(Lit 0 :*: _) -> Lit 0
(_ :*: Lit 0) -> Lit 0
(Iluminado 0: +: e) -> simplificar e
(e: +: Lit 0) -> simplificar e
(Lit 1: *: e) -> simplificar e
(e: *: Lit 1) -> simplificar e
La forma del código sigue de cerca los tipos y las reglas de simplificación se expresan de forma natural inmediata. El código es fácil de derivar y los tipos lo ayudan a cubrir todos los casos que necesita y hacen que sea más fácil extender el código con una funcionalidad adicional, algo que los entrevistadores adoran preguntar. (Con buena razón: ¡es algo que es increíblemente importante en la programación del mundo real también!)
Podría hacer todo esto en Python, por supuesto, pero sería más incómodo y doloroso. He experimentado esto de primera mano cuando la tarea para mi clase de lenguaje de programación estaba en Python. La historia de Haskell es mucho más agradable.
pereza
Otra faceta de Haskell que se destaca como particularmente expresiva es la pereza . Confiando en la pereza, podemos expresar ideas y abstracciones directamente que serían dolorosas sin ella.
Una ventaja es que podemos escribir algoritmos que deben evaluarse intercalados en fragmentos léxicamente separados. Esto, por ejemplo, nos da una función eficiente aparentemente trivial para seleccionar los principales elementos k de una lista desordenada:
select :: Ord a => Int -> [a] -> [a]
select k = take k . sort
Simplemente usamos nuestra función de clasificación normal y confiamos en la pereza para no ordenar toda la lista. Mientras la función de clasificación sea razonable en sí misma, esto tiene las asintóticas que queremos.
Un enfoque interesante, pero que limita con “lindo” y no es tan difícil en Python. (En parte porque Python tiene la pereza incorporada, ¡pero solo para listas, en forma de generadores!)
Queremos algo un poco más interesante, confiando en la pereza de maneras menos triviales. ¿Qué es la pereza buena en el modelado que es difícil sin ella? Infinito , especialmente infinito en el sentido de precisión arbitraria: piense en números reales. Aquí hay un problema interesante, quizás un poco cruel para una entrevista: diseñe un tipo de datos para almacenar las posiciones de los objetos en dos dimensiones con precisión arbitraria . Esto podría usarse, por ejemplo, para gráficos que son independientes de la resolución. Queremos indexar en un área continua ([math] \ mathbb {R} ^ 2 [/ math]) de una manera más simple y más general que algo como SVG.
Entonces cómo podemos hacer esto? Bueno, una forma razonable de representar datos de imagen en dos dimensiones es usar un quadtree. Un quadtree indexa un espacio bidimensional dividiéndolo repetidamente en cuadrantes. Las áreas que contienen más detalles se dividen en cuadrantes más pequeños y las áreas sin muchos detalles se dejan en una resolución más alta.
Un quadtree finito para un rayo. Imagen en el dominio público de Wikimedia.
Para obtener una resolución arbitraria, podemos usar un quadtree perezoso con una profundidad potencialmente ilimitada. Cuando necesitamos renderizarlo en una resolución dada, lo evaluamos hasta cierto límite, aproximándonos (es decir, suavizado) después de eso. El caso más simple, solo píxeles en blanco y negro, con “gris” como nuestra aproximación, es lo suficientemente corto como para caber cómodamente en una entrevista. Los casos más complejos, como los colores arbitrarios, serán más complicados y complicados, pero seguirán la misma idea general.
La razón por la que esto es fácil con Haskell es que los tipos de datos son vagos por defecto. Un quadtree potencialmente infinito que podemos evaluar en parte es … solo un quadtree normal:
data Quad = White
| Black
| Gray Quad Quad Quad Quad
Ser realmente capaz de hacer cuadráticos infinitamente profundos es realmente útil: podemos tener una función de círculo único que produzca un árbol cuádruple de un círculo que rinda lo mejor posible para cualquier resolución . Las mismas capacidades que SVG pero más simple y más general. Podríamos usar estos árboles infinitos como cualquier otro dato de imagen, combinándolos con otros cuadrantes y nunca perdiendo información hasta el final: las operaciones se componen sin problemas y cualquier redondeo es explícitamente parte de la representación, no parte de la representación de datos en sí.
Escribir operaciones sobre Quad es una cuestión de coincidencia de patrones y es bastante sencillo de una manera similar al evaluador de expresiones que mostré anteriormente.
Algunas operaciones requieren un poquito de inteligencia para mantenerlas flojas; desea evitar cualquier operación que requiera leer en toda la profundidad del árbol, como simplificar nodos iguales en otros más grandes. Pero tener esto en mente no es difícil, es algo que viene con un poco de práctica. Terminas con transformaciones de cuadrúpedos muy perezosas que puedes encadenar tanto como quieras y, gracias a la magia de la evaluación perezosa, solo se realizará una cantidad suficiente de cada paso para obtener el resultado final que deseas. ¡Nunca necesitas calcular todo, lo cual es genial porque todo podría extenderse para siempre!
Incluso esto ya va a ser significativamente más difícil sin pereza. Ni siquiera sabría por dónde comenzar en Python, excepto quizás tratando de emular a Haskell, mal. Pero en realidad podemos llevar este problema un paso más allá: ¿qué sucede si queremos expandir nuestro código para que tenga un alcance ilimitado ? Es decir, ¿qué pasa si no solo queremos apoyar resoluciones arbitrarias sino también
un lienzo infinito?
Para que esto funcione, por supuesto, no podemos almacenar todo el lienzo en la memoria, no tenemos que evaluar más de lo que necesitamos renderizar. Suena como más pereza!
¿Por qué es útil esto? Bueno, nos permite expresar cosas útiles como cuadrículas o curvas que llenan espacios o fractales o ruido de una manera que se puede combinar con otras imágenes, sin importar cuán grandes sean esas imágenes. Y la lógica es útil incluso si no nos importan las extensiones totalmente infinitas: nos permitirá realizar operaciones en imágenes grandes, reutilizar sub-partes de esas imágenes en otros lugares y luego solo calcular el mínimo que necesitamos para obtener cualquier resultado dado . El código de imagen escrito de esta manera es sumamente componible y modular .
Para obtener una resolución ilimitada, teníamos un árbol perezoso que podía extenderse tanto como quisiera. Para renderizarlo, solo evaluamos tan lejos como sea necesario para alcanzar nuestra resolución deseada, y luego nos aproximamos. Sin embargo, el área que estamos evaluando está inherentemente limitada: el árbol con el que comenzamos es el más grande y todos sus subárboles, una secuencia potencialmente infinita, representan regiones cada vez más pequeñas.
Lo que necesitamos es un árbol que sea perezoso en ambas direcciones: podemos viajar tan lejos como queramos y podemos viajar tan alto como queramos. Cuanto más alto vamos, más grande es la región cubierta. Para renderizar una región dada a una resolución dada, primero ascenderíamos lo suficientemente alto como para cubrir esa región y luego descenderíamos lo suficientemente bajo como para alcanzar nuestra resolución. En cada paso, confiamos en la pereza para no calcular nada extraño .
Para ser justos, esto sigue siendo complicado incluso en Haskell. Pero es accesible o incluso, si conoce la abstracción correcta, sistemática . Para subir y bajar un árbol (o cualquier otro tipo), podemos usar una cremallera y podemos derivar la cremallera para cualquier tipo mediante programación. (Fascinantemente, es el resultado de tomando la derivada del tipo ).
Confío bastante en estas ideas y podría resolverlas en Haskell en una entrevista, con algunas sugerencias y comentarios justos. Sería injusto esperar que alguien conozca todos los trucos, pero pasar de “quadtree perezoso” o “quadtree perezoso con cremallera” al tipo y los argumentos correctos es sumamente razonable. Eso es más o menos lo que hice: obtuve la idea de alto nivel del blog de Conal, pero podría pasar de eso a una implementación real.
Ni siquiera puedo comenzar a imaginar hacer esto en Python. En el mejor de los casos, podría resolver todos los detalles en Haskell e intentar portarlos a Python, pero dudo que pueda llegar allí sin tropezar con un montón de errores. Intentar emular la pereza, los tipos de datos algebraicos y la coincidencia de patrones en un lenguaje que no admite ninguno de ellos es lamentable.
Entonces, hay un gran ejemplo de algo más fácil en Haskell que en Python: una representación de imagen con área ilimitada y resolución ilimitada , que nos permite componer y manipular imágenes sin perder ninguna información en el camino y finalmente calcular exactamente lo que necesitamos para renderizarlas sin hacer trabajo extraño
Creo que eso es genial. Y podría encajar totalmente una versión básica en una pregunta de entrevista. Pero si estás entrevistando a personas que no son auténticas con la pereza, es sádico y cruel.
