Haskell - reproduzir a remodelação de numpy

Entrando em Haskell, estou tentando reproduzir algo como a remodelação de numpy com listas. Especificamente, dada uma lista simples, reformule-a em uma 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]]])

Consegui reproduzir o comportamento com índices fixos, por exemplo:

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

Meu código é:

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

Agora, parece que não consigo encontrar uma maneira de generalizar isso para uma forma arbitrária. Minha ideia original era fazer uma dobra:

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

Mas, não importa como eu faça isso, sempre recebo um erro de tipo do compilador. Pelo que entendi, o problema é que, em algum momento, o tipo for accé inferido como idie a -> a, e não gosta do fato de que a lista de funções na dobra tem um tipo diferente (embora compatível com a composição) assinatura. Eu me deparo com o mesmo problema tentando implementar isso com recursão em vez de uma dobra. Isso me confundiu porque originalmente eu tinha pretendido para o [b]em reshape's assinatura de tipo para ser um stand-in para 'um outro, tipo dissociada', que poderia ser qualquer coisa, desde [[a]]a [[[[[a]]]]].

Como estou indo errado sobre isso? Existe uma maneira de realmente alcançar o comportamento que eu pretendia, ou é simplesmente errado querer esse tipo de comportamento "dinâmico" em primeiro lugar?

Existem dois detalhes aqui que são qualitativamente diferentes do Python, em última análise, decorrentes da digitação dinâmica versus estática.

O primeiro que você notou: em cada etapa do chunking, o tipo resultante é diferente do tipo de entrada. Isso significa que você não pode usar foldr, porque espera uma função de um tipo específico. Você poderia fazê-lo via recursão.

O segundo problema é um pouco menos óbvio: o tipo de retorno da sua reshapefunção depende de qual é o primeiro argumento. Por exemplo, se o primeiro argumento for [2], o tipo de retorno será [[a]], mas se o primeiro argumento for [2, 3], o tipo de retorno será [[[a]]]. No Haskell, todos os tipos devem ser conhecidos em tempo de compilação. E isso significa que sua reshapefunção não pode receber o primeiro argumento definido em tempo de execução. Em outras palavras, o primeiro argumento deve estar no nível do tipo.

Os valores no nível de tipo podem ser calculados por meio de funções de tipo (também conhecidas como "famílias de tipos"), mas como não é apenas o tipo (ou seja, você também tem um valor para calcular), o mecanismo natural (ou o único?) Para esse tipo é um tipo classe.

Então, primeiro vamos definir nossa classe de tipo:

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

A classe possui três parâmetros: dimensionskind [Nat]é uma matriz de números no nível de tipo, representando as dimensões desejadas. fromé o tipo de argumento e toé o tipo de resultado. Observe que, mesmo sabendo que o tipo de argumento é sempre [a], temos que tê-lo como uma variável de tipo aqui, porque, caso contrário, nossas instâncias de classe não conseguirão corresponder corretamente o mesmo aentre argumento e resultado.

Além disso, a classe tem uma dependência funcional dimensions from -> topara indicar que se eu sei tanto dimensionse from, posso inequivocamente determinar to.

A seguir, o caso base: quando dimentionshá uma lista vazia, a função apenas se degrada para id:

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

E agora a carne: o 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

Primeiro, ele faz a chamada recursiva reshape @tailpara dividir a dimensão anterior e, em seguida, separa o resultado usando o valor da dimensão atual como tamanho do bloco.

Observe também que estou usando a chunksOffunção da bibliotecasplit . Não há necessidade de redefinir você mesmo.

Vamos testá-lo:

λ 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]]]]

Para referência, veja o programa completo com todas as importações e extensões:

{-# 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

A resposta de @Fyodor Soikin é perfeita com relação à pergunta real. Exceto que há um pouco de problema com a própria pergunta. Listas de listas não é a mesma coisa que uma matriz. É um equívoco comum que Haskell não tenha matrizes e você seja forçado a lidar com listas, o que não poderia estar mais longe da verdade.

Como a pergunta está marcada arraye existe uma comparação com numpy, eu gostaria de adicionar uma resposta adequada que lide com essa situação para matrizes multidimensionais. Existem algumas bibliotecas de matriz no ecossistema Haskell, uma das quais émassiv

Uma reshapefuncionalidade semelhante numpypode ser alcançada por resize'função:

λ> 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 ]
    ]
  ]