Haskell - Reproduzieren Sie die Umformung von Numpy

Wenn ich nach Haskell komme, versuche ich, so etwas wie Numpys Umformung mit Listen zu reproduzieren . Wenn Sie eine flache Liste haben, formen Sie sie in eine n-dimensionale Liste um:

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

Ich konnte das Verhalten mit festen Indizes reproduzieren, zB:

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

Mein Code lautet:

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

Jetzt kann ich anscheinend keinen Weg finden, dies auf eine beliebige Form zu verallgemeinern. Meine ursprüngliche Idee war eine Falte:

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

Aber egal wie ich vorgehe, ich bekomme immer einen Tippfehler vom Compiler. Nach meinem Verständnis besteht das Problem darin, dass der Typ für irgendwann accals id's' abgeleitet wird a -> a, und es gefällt nicht, dass die Liste der Funktionen in der Falte alle einen anderen (obwohl für die Komposition kompatiblen) Typ hat Unterschrift. Ich habe das gleiche Problem, wenn ich versuche, dies mit Rekursion selbst anstelle einer Falte zu implementieren. Die verwirrte mich , weil ich ursprünglich für die beabsichtigt hatte , [b]in reshape‚s - Typ Unterschrift ein Stand-in für‚einen anderen, dissoziierten Typen‘zu sein , die alles von könnten [[a]]zu [[[[[a]]]]].

Wie mache ich das falsch? Gibt es eine Möglichkeit, das von mir beabsichtigte Verhalten tatsächlich zu erreichen, oder ist es einfach falsch, diese Art von "dynamischem" Verhalten überhaupt zu wollen?

Hier gibt es zwei Details, die sich qualitativ von Python unterscheiden und sich letztendlich aus der dynamischen oder statischen Typisierung ergeben.

Der erste, den Sie selbst bemerkt haben: Bei jedem Chunking-Schritt unterscheidet sich der resultierende Typ vom Eingabetyp. Dies bedeutet, dass Sie nicht verwenden können foldr, da eine Funktion eines bestimmten Typs erwartet wird. Sie können dies jedoch durch Rekursion tun.

Das zweite Problem ist etwas weniger offensichtlich: Der Rückgabetyp Ihrer reshapeFunktion hängt vom ersten Argument ab. Wenn das erste Argument ist [2], ist der Rückgabetyp [[a]], aber wenn das erste Argument ist [2, 3], ist der Rückgabetyp [[[a]]]. In Haskell müssen alle Typen zur Kompilierungszeit bekannt sein. Dies bedeutet, dass Ihre reshapeFunktion nicht das erste zur Laufzeit definierte Argument verwenden kann. Mit anderen Worten, das erste Argument muss auf Typebene liegen.

Werte auf Typebene können über Typfunktionen (auch als "Typfamilien" bezeichnet) berechnet werden. Da es sich jedoch nicht nur um den Typ handelt (dh Sie müssen auch einen Wert berechnen), ist der natürliche (oder einzige?) Mechanismus dafür ein Typ Klasse.

Definieren wir zunächst unsere Typklasse:

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

Die Klasse hat drei Parameter: dimensionsArt [Nat]ist ein Array von Zahlen auf Typebene, die die gewünschten Dimensionen darstellen. fromist der Argumenttyp und toder Ergebnistyp. Beachten Sie, dass [a]wir , obwohl bekannt ist, dass der Argumenttyp immer ist , ihn hier als Typvariable haben müssen, da unsere Klasseninstanzen sonst nicht in der Lage sind, den gleichen Typ azwischen Argument und Ergebnis zu finden.

Außerdem hat die Klasse eine funktionale Abhängigkeit dimensions from -> to, die angibt, dass ich eindeutig bestimmen kann , ob ich beide dimensionsund kenne .fromto

Als nächstes der Basisfall: Wenn dimentionses sich um eine leere Liste handelt, wird die Funktion nur auf Folgendes herabgesetzt id:

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

Und jetzt das Fleisch: der rekursive Fall.

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

Zuerst wird der rekursive Aufruf ausgeführt reshape @tail, um die vorherige Dimension zu entfernen, und dann wird das Ergebnis unter Verwendung des Werts der aktuellen Dimension als Blockgröße aufgeteilt.

Beachten Sie auch, dass ich die chunksOfFunktion aus der Bibliothek verwendesplit . Sie müssen es nicht selbst neu definieren.

Probieren wir es aus:

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

Als Referenz finden Sie hier das vollständige Programm mit allen Importen und Erweiterungen:

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

@Fyodor Soikins Antwort ist perfekt in Bezug auf die eigentliche Frage. Außer es gibt ein kleines Problem mit der Frage selbst. Listen von Listen sind nicht dasselbe wie ein Array. Es ist ein weit verbreitetes Missverständnis, dass Haskell keine Arrays hat und Sie gezwungen sind, sich mit Listen zu befassen, die nicht weiter von der Wahrheit entfernt sein könnten.

Da die Frage mit markiert ist arrayund es einen Vergleich mit gibt numpy, möchte ich eine richtige Antwort hinzufügen, die diese Situation für mehrdimensionale Arrays behandelt. Es gibt einige Array-Bibliotheken im Haskell-Ökosystem, von denen eine istmassiv

Eine reshapeähnliche Funktionalität von numpykann durch resize'Funktion erreicht werden :

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