时间戳

首页 > 解决方案 > Haskell - 重现 numpy 的重塑

arrays - Haskell - 重现 numpy 的重塑

问题描述

进入 Haskell，我试图用列表重现numpy 的 reshape 之类的东西。具体来说，给定一个平面列表，将其重塑为一个 n 维列表：

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

我能够重现具有固定索引的行为，例如：

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

我的代码是：

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

现在，我似乎找不到将其推广到任意形状的方法。我最初的想法是折叠：

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

但是，无论我怎么做，我总是从编译器那里得到一个类型错误。据我了解，问题在于，在某些时候，类型 foracc被推断为id' ie a -> a，并且它不喜欢折叠中的函数列表都具有不同（尽管与组合兼容）类型的事实签名。我遇到了同样的问题，试图自己用递归而不是折叠来实现它。这让我很困惑，因为最初我打算让[b]inreshape的类型签名成为“另一种分离的类型”的替代品，它可以是从[[a]]to 的任何东西[[[[[a]]]]]。

我怎么错了？有没有办法真正实现我想要的行为，或者首先想要这种“动态”行为是完全错误的？

标签： arraysnumpyhaskell

解决方案

这里有两个细节与 Python 有本质上的不同，最终源于动态与静态类型。

您自己注意到的第一个问题：在每个分块步骤中，结果类型与输入类型不同。这意味着您不能使用foldr，因为它需要一个特定类型的函数。你可以通过递归来做到这一点。

第二个问题不太明显：reshape函数的返回类型取决于第一个参数是什么。就像，如果第一个参数是[2]，则返回类型是[[a]]，但如果第一个参数是[2, 3]，那么返回类型是[[[a]]]。在 Haskell 中，所有类型在编译时都必须是已知的。这意味着您的reshape函数不能采用在运行时定义的第一个参数。换句话说，第一个参数必须在类型级别。

类型级别的值可以通过类型函数（也称为“类型族”）计算，但因为它不仅仅是类型（即你也有一个值要计算），自然（或唯一？）机制是类型班级。

所以，首先让我们定义我们的类型类：

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

该类具有三个参数：dimensionsof kind[Nat]是一个类型级别的数字数组，表示所需的维度。from是参数类型，to是结果类型。请注意，即使已知参数类型始终为[a]，我们也必须在此处将其作为类型变量，否则我们的类实例将无法正确匹配a参数和结果之间的相同。

另外，该类具有函数依赖关系dimensions from -> to，表明如果我知道dimensions和from，我可以明确地确定to。

接下来，基本情况：当dimentions是一个空列表时，函数会降级为id：

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

首先，它进行递归调用reshape @tail以分块前一个维度，然后使用当前维度的值作为块大小来分块结果。

另请注意，我正在使用chunksOf库中的函数split。无需自己重新定义。

让我们测试一下：

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

作为参考，这是包含所有导入和扩展的完整程序：

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

推荐阅读