Haskell 组合映射的多态递归导致无限类型错误

Question

创建可以动态创建组合地图的函数的正确方法是什么？

这会导致错误（也发生在 fmap 中）：

createComposedMaps list = accumulate list map
    where 
        accumulate (x:xs) m = accumulate xs (m.map)
        accumulate []     m = m

与list无关，只是统计作文的数量

我得到的错误是关于 "cannot construct infinite type":

Occurs check: cannot construct the infinite type: a2 ~ [a2]
Expected type: (a2 -> b1) -> a2 -> b1
  Actual type: (a2 -> b1) -> [a2] -> [b1]
Relevant bindings include
  m :: (a2 -> b1) -> c (bound at dimensional_filter.hs:166:27)
  accumulate :: [t1] -> ((a2 -> b1) -> c) -> (a2 -> b1) -> c
    (bound at dimensional_filter.hs:166:9)
In the second argument of ‘(.)’, namely ‘map’
In the second argument of ‘accumulate’, namely ‘(m . map)’

Occurs check: cannot construct the infinite type: b1 ~ [b1]
Expected type: (a2 -> b1) -> a2 -> b1
  Actual type: (a2 -> b1) -> [a2] -> [b1]
Relevant bindings include
  m :: (a2 -> b1) -> c (bound at dimensional_filter.hs:166:27)
  accumulate :: [t1] -> ((a2 -> b1) -> c) -> (a2 -> b1) -> c
    (bound at dimensional_filter.hs:166:9)
In the second argument of ‘(.)’, namely ‘map’
In the second argument of ‘accumulate’, namely ‘(m . map)’

目标是创建一个我以后可以使用的动态组合映射函数。而其他半群可以附加在一起（列表，数字......）。函数好像难多了

希望有一个显示 fmap and/or 地图的示例。

我找到了这个Library function to compose a function with itself n times

但我需要使用每个中间构图，而不仅仅是最终构图。一些例子仍然给我无限的类型错误。

原来问题可能涉及多态递归。随着 accumulate 函数的每次递归应用都会更改地图类型。

Answer 1

这是依赖类型的经典工作，这意味着我们根据参数值计算 return 类型。在这里我们想表达结果列表的嵌套取决于数字输入（在您的情况下，您使用列表参数的长度作为数字输入，但最好只在需要数字的地方使用数字） .

不幸的是，Haskell 还没有对依赖类型的适当支持，并且现有的变通解决方案涉及一些样板和并发症。 Idris 是一种具有类似 Haskell 语法和完全依赖类型的语言，因此我可以更清楚地说明 Idris 中的想法：

-- unary naturals from the Idris Prelude :
-- data Nat = Z | S Nat

-- compose a function n times (which can also be a type constructor!)
-- for example, iterN 3 List Int = List (List (List Int))
iterN : Nat -> (a -> a) -> a -> a
iterN Z     f a = a
iterN (S k) f a = f (iterN k f a)

mapN : (n : Nat) -> (a -> b) -> iterN n List a -> iterN n List b
mapN Z     f as = f as
mapN (S k) f as = map (mapN k f) as

-- usage:
> mapN 3 (+10) [[[0]]]
[[[10]]]
> mapN 0 id 10
10

这是完整的 Idris 解决方案。在 Haskell 中，我们不能在类型中有值或函数，实现上述工作的唯一方法是将函数的类型级版本创建为类型族，将类型的值级版本创建为单例，有效地编写两倍于理想数量的定义。 singletons 库试图通过模板 Haskell 和巧妙的机制删除大量样板文件。这是一个基于单例的解决方案：

{-# LANGUAGE DataKinds, TypeFamilies #-}

import Data.Singletons -- package: singletons
import Data.Nat        -- package: singleton-nats (by me)

type family IterN n f a where
  IterN Z     f a = a
  IterN (S n) f a = f (IterN n f a)

mapN :: Sing n -> (a -> b) -> IterN n [] a -> IterN n [] b  
mapN SZ     f a  = f a
mapN (SS n) f as = map (mapN n f) as

-- usage:
> mapN (sing :: SLit 3) (+10) [[[0]]]
[[[10]]]

好消息是，我们正在进行研究和开发以向 GHC 添加依赖类型，我们可以期待在未来几年内有所改进。

或者，人们可能会想使用类型类来推断 return 类型中的嵌套量。这是相当可怕的，因为我们必须区分 [a] 和非列表类型，这至少需要 OverlappingInstances，但实际上它可以接受更差的 IncoherentInstances，因为我们还想根据本地上下文解析多态类型。

{-# LANGUAGE
  UndecidableInstances, IncoherentInstances, MultiParamTypeClasses,
  FlexibleInstances, TypeFamilies #-}

class MapN a b as bs where
  mapN :: (a -> b) -> as -> bs

instance (as ~ a, bs ~ b) => MapN a b as bs where
  mapN = id

instance (MapN a b as bs, bs' ~ [bs]) => MapN a b [as] bs' where
  mapN f as = map (mapN f) as

-- usage:
> mapN (+1) 0
1
> mapN (+10) [[[0]]]
[[[10]]]

-- note though that without enough context `mapN`'s type is nonsense:
> :t mapN (+0)
mapN (+0) :: Num b => b -> b

Haskell 组合映射的多态递归导致无限类型错误

Haskell Polymorphic Recursion with Composed Maps causes Infinite Type Error

polymorphism

recursion

haskell

types

composition