example - haskell $ operator

Haskell: `Mapa(a, b) c` contra` Mapa a(Mapa bc) `?

Question

Pensando en los mapas como representaciones de funciones finitas, se puede dar un mapa de dos o más variables en currículum o no; es decir, los tipos Map (a,b) c y Map a (Map bc) son isomorfos, o algo parecido.

¿Qué consideraciones prácticas hay -eficiencia, etc.- para elegir entre las dos representaciones?

Answer 1

La instancia de Ord de tuplas usa un orden lexicográfico, por lo que Map (a, b) c va a ordenar por a primera de todas formas, por lo que el orden general será el mismo. En cuanto a las consideraciones prácticas:

• Debido a que Data.Map es un árbol de búsqueda binaria que se divide en una clave es comparable a una búsqueda, por lo que obtener un submapa para una dada en la forma no cursiva no será significativamente más caro que en la forma al curry.

• La forma al curry puede producir un árbol menos equilibrado en general, por la razón obvia de tener varios árboles en lugar de solo uno.

• La forma al curry tendrá un poco de sobrecarga adicional para almacenar los mapas anidados.

• Los mapas anidados de curris que representan "aplicaciones parciales" se pueden compartir si algunos valores a producen el mismo resultado.

• De manera similar, la "aplicación parcial" de la forma al curry le proporciona el mapa interno existente, mientras que la forma no surcada debe construir un nuevo mapa.

Por lo tanto, la forma no revisada es claramente mejor en general , pero la forma al curry puede ser mejor si esperas hacer una "aplicación parcial" a menudo y se beneficiaría al compartir los valores de Map bc .

Tenga en cuenta que será necesario cierto cuidado para asegurarse de que realmente se beneficie de ese intercambio potencial; Tendrá que definir explícitamente cualquier mapa interno compartido y reutilizar el valor único al construir el mapa completo.

Editar: Tikhon Jelvis señala en los comentarios que la sobrecarga de memoria de los constructores de tuplas -que no pensé en explicar- no es para nada despreciable. Ciertamente hay algo de sobrecarga para la forma currificada, pero esa sobrecarga es proporcional a la cantidad de valores distintos que existen. La sobrecarga del constructor de tuplas en la forma no cursiva, por otro lado, es proporcional al número total de claves.

Entonces, si, en promedio, para cualquier valor dado de a hay tres o más teclas distintas que lo usan, probablemente guarde la memoria con la versión curried. Las preocupaciones sobre los árboles desequilibrados todavía se aplican, por supuesto. Cuanto más lo pienso, más sospecho que la forma currículum es inequívocamente mejor, excepto quizás si tus claves son muy dispersas y están distribuidas de manera desigual.

Tenga en cuenta que debido a que una gran cantidad de definiciones le importan a GHC, se requiere el mismo cuidado al definir funciones si desea que las subexpresiones se compartan; esta es una de las razones por las que algunas veces ve funciones definidas en un estilo como este:

foo x = go
  where z = expensiveComputation x
        go y = doStuff y z

Answer 2

Las tuplas son flojas en ambos elementos, por lo que la versión de tupla introduce un poco de pereza adicional. Si esto es bueno o malo, depende en gran medida de su uso. (En particular, las comparaciones pueden forzar los elementos de tupla, pero solo si hay muchos valores duplicados).

Más allá de eso, creo que va a depender de cuántos duplicados tengas. Si a es casi siempre diferente cuando b es, vas a tener muchos árboles pequeños, por lo que la versión de la tupla podría ser mejor. Por otro lado, si sucede lo contrario, la versión no tuple puede ahorrarle un poco de tiempo (no recomponer constantemente a vez que haya encontrado el subárbol apropiado y esté buscando b ).

Me acuerdo de los intentos y de cómo almacenan los prefijos comunes una vez. La versión no-tupla parece ser un poco así. Un trie puede ser más eficiente que un BST si hay muchos prefijos comunes y menos eficiente si no los hay.

Pero el resultado final es un punto de referencia !! ;-)

Answer 3

Además de los aspectos de eficiencia, esta pregunta también tiene un lado pragmático: ¿qué quieres hacer con esta estructura?

¿Quiere, por ejemplo, poder almacenar un mapa vacío para un valor dado de tipo a ? Si es así, ¡la versión no revisada podría ser más práctica!

Aquí hay un ejemplo simple: digamos que queremos almacenar las propiedades de las personas con valores de String , digamos el valor de algunos campos en la página del perfil de esa persona.

type Person = String
type Property = String

uncurriedMap :: Map Person (Map Property String)
uncurriedMap = fromList [
                   ("yatima2975", fromList [("location","Utrecht"),("age","37")]),
                   ("PLL", fromList []) ]
curriedMap :: Map (Person,Property) String
curriedMap = fromList [
                 (("yatima2975","location"), "Utrecht"),
                 (("yatima2975","age"), "37") ]

Con la versión curried, no hay una forma agradable de registrar el hecho de que el usuario conoce el "PLL" , pero no ha completado ninguna información. Un par de persona / propiedad ("PLL",undefined) va a causar bloqueos en tiempo de ejecución, ya que Map es estricto en las claves.

Puede cambiar el tipo de curriedMap a Map (Person,Property) (Maybe String) y almacenar Nothing s allí, y esa podría ser la mejor solución en este caso; pero donde hay un número desconocido / variable de propiedades (por ejemplo, dependiendo del tipo de persona) que también se encontrará con dificultades.

Entonces, supongo que también depende de si necesita una función de consulta como esta:

data QueryResult = PersonUnknown | PropertyUnknownForPerson | Value String
query :: Person -> Property -> Map (Person, Property) String -> QueryResult

Esto es difícil de escribir (si no imposible) en la versión curried, pero fácil en la versión no cursiva.