Al ingresar a Haskell, estoy tratando de reproducir algo como nueva forma de numpy con listas. Específicamente, dada una lista plana, reconfórmela en una lista n-dimensional:

import numpy as np

a = np.arange(1, 18)
b = a.reshape([-1, 2, 3])

# b = 
# 
# array([[[ 1,  2,  3],
#         [ 4,  5,  6]],
# 
#        [[ 7,  8,  9],
#         [10, 11, 12]],
# 
#        [[13, 14, 15],
#         [16, 17, 18]]])

Pude reproducir el comportamiento con índices fijos, por ejemplo:

*Main> reshape23 [1..18]
[[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]],[[13,14,15],[16,17,18]]]

Mi código es:

takeWithRemainder :: (Integral n) => n -> [a] -> ([a], [a])
takeWithRemainder _ [] = ([], [])
takeWithRemainder 0 xs = ([], xs)
takeWithRemainder n (x:xs) = (x : taken, remaining)
                                where (taken, remaining) = takeWithRemainder (n-1) xs

chunks :: (Integral n) => n -> [a] -> [[a]]
chunks _ [] = []
chunks chunkSize xs = chunk : chunks chunkSize remainderOfList
                        where (chunk, remainderOfList) = takeWithRemainder chunkSize xs

reshape23 = chunks 2 . chunks 3

Ahora, parece que no puedo encontrar una manera de generalizar esto a una forma arbitraria. Mi idea original era hacer un pliegue:

reshape :: (Integral n) => [n] -> [a] -> [b]
reshape ns list = foldr (\n acc -> (chunks n) . acc) id ns list

Pero, no importa cómo lo haga, siempre obtengo un error de tipo del compilador. Según tengo entendido, el problema es que en algún momento se infiere que el tipo de acc es id, es decir, a -> a, y no le gusta el hecho de que la lista de todas las funciones en el pliegue tienen una firma de tipo diferente (aunque compatible para la composición). Me encuentro con el mismo problema tratando de implementar esto con recursividad yo mismo en lugar de un pliegue. Esto me confundió porque originalmente tenía la intención de que [b] en la firma de tipo de reshape fuera un sustituto de "otro tipo disociado" que podría ser desde [[a]] hasta { {X6}}.

¿Cómo me estoy equivocando sobre esto? ¿Hay alguna manera de lograr realmente el comportamiento que pretendía, o es simplemente erróneo querer este tipo de comportamiento "dinámico" en primer lugar?

8
shost71 10 feb. 2020 a las 08:33

2 respuestas

La mejor respuesta

Aquí hay dos detalles que son cualitativamente diferentes de Python, que en última instancia se derivan de la escritura dinámica frente a la estática.

El primero lo ha notado usted mismo: en cada paso de fragmentación, el tipo resultante es diferente del tipo de entrada. Esto significa que no puede usar foldr, porque espera una función de un tipo específico. Sin embargo, podría hacerlo a través de la recursión.

El segundo problema es un poco menos obvio: el tipo de retorno de su función reshape depende de cuál sea el primer argumento. Como, si el primer argumento es [2], el tipo de retorno es [[a]], pero si el primer argumento es [2, 3], entonces el tipo de retorno es [[[a]]]. En Haskell, todos los tipos deben conocerse en tiempo de compilación. Y esto significa que su función reshape no puede tomar el primer argumento que se define en tiempo de ejecución. En otras palabras, el primer argumento debe estar en el nivel de tipo.

Los valores de nivel de tipo pueden calcularse mediante funciones de tipo (también conocidas como "familias de tipos"), pero debido a que no es solo el tipo (es decir, también tiene un valor para calcular), ¿el natural (o el único? ) mecanismo para eso es una clase de tipo.

Entonces, primero definamos nuestra clase de tipo:

class Reshape (dimensions :: [Nat]) from to | dimensions from -> to where
    reshape :: from -> to

La clase tiene tres parámetros: dimensions del tipo [Nat] es una matriz de números a nivel de tipo, que representa las dimensiones deseadas. from es el tipo de argumento y to es el tipo de resultado. Tenga en cuenta que, aunque se sabe que el tipo de argumento siempre es [a], tenemos que tenerlo como una variable de tipo aquí, porque de lo contrario nuestras instancias de clase no podrán coincidir correctamente con el mismo {{X5} } entre argumento y resultado.

Además, la clase tiene una dependencia funcional dimensions from -> to para indicar que si conozco tanto dimensions como from, puedo determinar sin ambigüedades to.

A continuación, el caso base: cuando dimentions es una lista vacía, la función simplemente se degrada a id:

instance Reshape '[] [a] [a] where
    reshape = id

Y ahora la carne: el caso recursivo.

instance (KnownNat n, Reshape tail [a] [b]) => Reshape (n:tail) [a] [[b]] where
    reshape = chunksOf n . reshape @tail
        where n = fromInteger . natVal $ Proxy @n

Primero realiza la llamada recursiva reshape @tail para fragmentar la dimensión anterior, y luego fragmenta el resultado de eso utilizando el valor de la dimensión actual como tamaño de fragmentación.

Tenga en cuenta también que estoy usando el chunksOf función de la biblioteca split. No hay necesidad de redefinirlo usted mismo.

Probémoslo:

λ reshape @ '[1] [1,2,3]          
[[1],[2],[3]]                     

λ reshape @ '[1,2] [1,2,3,4]        
[[[1,2]],[[3,4]]]                   

λ reshape @ '[2,3] [1..12]              
[[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]]]

λ reshape @ '[2,3,4] [1..24]                                                      
[[[[1,2,3,4],[5,6,7,8],[9,10,11,12]],[[13,14,15,16],[17,18,19,20],[21,22,23,24]]]]

Como referencia, aquí está el programa completo con todas las importaciones y extensiones:

{-# LANGUAGE
    MultiParamTypeClasses, FunctionalDependencies, TypeApplications,
    ScopedTypeVariables, DataKinds, TypeOperators, KindSignatures,
    FlexibleInstances, FlexibleContexts, UndecidableInstances,
    AllowAmbiguousTypes
#-}

import Data.Proxy (Proxy(..))
import Data.List.Split (chunksOf)
import GHC.TypeLits (Nat, KnownNat, natVal)

class Reshape (dimensions :: [Nat]) from to | dimensions from -> to where
    reshape :: from -> to

instance Reshape '[] [a] [a] where
    reshape = id

instance (KnownNat n, Reshape tail [a] [b]) => Reshape (n:tail) [a] [[b]] where
    reshape = chunksOf n . reshape @tail
        where n = fromInteger . natVal $ Proxy @n
10
Fyodor Soikin 11 feb. 2020 a las 01:53

La respuesta de @Fyodor Soikin es perfecta con respecto a la pregunta real. Excepto que hay un pequeño problema con la pregunta en sí. Las listas de listas no son lo mismo que una matriz. Es un error común pensar que Haskell no tiene matrices y que se ve obligado a lidiar con listas, que no podrían estar más lejos de la realidad.

Debido a que la pregunta está etiquetada con array y hay una comparación con numpy, me gustaría agregar una respuesta adecuada que maneje esta situación para las matrices multidimensionales. Hay un par de bibliotecas de matrices en el ecosistema de Haskell, una de las cuales es massiv

función resize' :

λ> 1 ... (18 :: Int)
Array D Seq (Sz1 18)
  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 ]
λ> resize' (Sz (3 :> 2 :. 3)) (1 ... (18 :: Int))
Array D Seq (Sz (3 :> 2 :. 3))
  [ [ [ 1, 2, 3 ]
    , [ 4, 5, 6 ]
    ]
  , [ [ 7, 8, 9 ]
    , [ 10, 11, 12 ]
    ]
  , [ [ 13, 14, 15 ]
    , [ 16, 17, 18 ]
    ]
  ]
6
lehins 10 feb. 2020 a las 11:00