如何编写解码器将JSON嵌套列表解码为递归定义的NestedList类型？

首先明确给定的递归类型定义：

type NestedList a
    = Elem a
    | SubList (List (NestedList a))

我们需要实现一个解码器，能把嵌套的JSON列表（比如 [1, [[2, [3, 4]], 5], 6, [7, 8, 9]]）解码成上述类型的实例，最终得到：

SubList
    [ Elem 1
    , SubList [ SubList [ Elem 2, SubList [ Elem 3, Elem 4 ] ], Elem 5 ]
    , Elem 6
    , SubList [ Elem 7, Elem 8, Elem 9 ]
    ]

核心思路：递归解码器 + 延迟求值 #

因为NestedList是递归类型，直接写递归解码器会导致初始化时的无限递归问题，所以必须用延迟求值包装递归调用。下面以Elm的Json.Decode库为例实现：

import Json.Decode as Decode exposing (Decoder, int, list, lazy, oneOf)

type NestedList a
    = Elem a
    | SubList (List (NestedList a))

-- 通用的NestedList解码器，接收基础元素的解码器作为参数
nestedListDecoder : Decoder a -> Decoder (NestedList a)
nestedListDecoder itemDecoder =
    oneOf
        -- 情况1：JSON值是单个元素，解码为Elem
        [ Decode.map Elem itemDecoder
        -- 情况2：JSON值是列表，解码为SubList；用lazy延迟递归调用，避免死循环
        , Decode.map SubList (list (lazy (\_ -> nestedListDecoder itemDecoder)))
        ]

代码说明 #

• oneOf：匹配两种JSON结构——单个基础元素，或者嵌套的列表
• lazy：把递归解码器的创建包装成函数，只有实际解码到列表时才执行，解决递归类型解码器的初始化死循环问题
• itemDecoder：解码基础元素的解码器，比如解码整数传int，解码字符串传string

测试示例 #

用整数解码器测试目标JSON：

Decode.decodeString (nestedListDecoder int) "[1, [[2, [3, 4]], 5], 6, [7, 8, 9]]"

执行后就能得到题目要求的NestedList Int实例。

其他语言实现思路（以Haskell为例） #

如果用Haskell的aeson库，核心逻辑类似，利用<|>组合两个解码器分别处理单个元素和列表：

{-# LANGUAGE DeriveGeneric #-}
import Data.Aeson
import GHC.Generics

data NestedList a = Elem a | SubList [NestedList a] deriving (Generic, Show)

instance FromJSON a => FromJSON (NestedList a) where
    parseJSON v =
        -- 先尝试解码为单个元素（Elem），失败则尝试解码为列表（SubList）
        (Elem <$> parseJSON v) <|> (SubList <$> parseJSON v)

内容的提问来源于stack exchange，提问作者Robert L