迭代嵌套的记录/字典OCaml

Question

很抱歉问了一个荒谬的问题，但我是OCaml的完全初学者。

我有两个类型:

type other = A | B
type someType = {a:string ; b:string ; c:other ; d:someType array}

我怎么能通过一个记录迭代并得到一个键的所有出现?

因为我不知道这个结构有多深，所以我不知道我需要在每个数组中循环多少次才能得到键。

let test = 
{a = "a"; b = "b"; c = B;
d =
[|{a = "aa"; b = "bb"; c = A;
d =
[|{a = "aaa"; b = "bbb"; c = A;
d =
[|{a = "aaaa"; b = "bbbb"; c = A; d = [||]};
{a = "aaaaa"; b = "bbbbb"; c = B; d = [||]}|]}|]}|]}

我想计算所有的a键并按c键排序。在这个例子中，我有5个a键，2个类型为B, 3个类型为a。我想以int * int = (3,2)

的形式返回它们。

Answer 1

OCaml中的记录不像Python中的字典，所以你不能真正遍历它们。从某种意义上说，记录更像是一个类，它是一个类型而不是一个值。

与python字典对应的是map数据结构。由于OCaml是一种静态类型语言，因此每个键/值类型都有单独的数据类型。你可以使用Map。为给定的键类型定义映射结构，例如

module Strings = Map.Make(String)

现在我们可以创建一个示例字典

let family = Strings.of_seq @@ List.to_seq [
"Alice", 30;
"Bob", 32;
"Charlie", 8;
"Daniel", 12;
]

要进行迭代，可以使用string对象。iter函数,

let () = family |> Strings.iter (fun name age ->
Format.printf "%s is %d years oldn" name age)

或者，由于OCaml是一种柯里化语言，所以只需

let () = family |> Strings.iter (Format.printf "%s is %d years oldn")

Answer 2

考虑基本条件:根本没有嵌套。d字段中的数组为空。如果字段c是A，那么您将返回(1, 0)。否则，如果是B,(0, 1).

简单的。

let rec count_c_keys {c; d; _} =
match c, d with
| A, [||] -> (1, 0)
| B, [||] -> (0, 1)

但是如果d不是一个空数组呢?然后将函数映射到该数组。

d |> Array.map count_c_keys

但是这将给我们一个元组数组。如何将元组数组变为可以添加到(1, 0)或(0, 1)的元组?

数组。Fold_left可以很好地工作。

let sum_2tuples_array =
let add_tuples (a, b) (c, d) = (a + c, b + d) in 
Array.fold_left add_tuples (0, 0)

现在，我们可以将someType array转换为(int * int) array，并从那里转换为int * int元组。一旦我们完成了这一点，通过一些模式匹配，根据c字段是否遇到A或B，为每个元素添加1就很简单了。

let rec count_c_keys {c; d; _} =
let sum_2tuples_array = 
let add_tuples (a, b) (c, d) = (a + c, b + d) in
Array.fold_left add_tuples (0, 0) 
in
match c, d with
| A, [||] -> (1, 0)
| B, [||] -> (0, 1)
| A, _ -> 
let (a_s, b_s) = d 
|> Array.map count_c_keys 
|> sum_2tuples_array 
in
(1 + a_s, b_s)
| B, _ -> 
let (a_s, b_s) = d 
|> Array.map count_c_keys 
|> sum_2tuples_array 
in
(a_s, 1 + b_s)

utop # count_c_keys test;;
- : int * int = (3, 2)

Answer 3

那么，如果我理解正确的话，你的问题在于递归结构。

因此这是一个递归问题。@glennsl的评论给了你一些问题，可以帮助你找到解决方案。

如何处理类型为someType的最内层元素?这个元素有一个特殊的值d?

作为一个例子，我将使用list而不是array。如果我想把所有的x放到 里

type spList = {x:xType ; l:spList list};;

我认为最里面的元素是l的空列表元素。在这种情况下，我将只将x作为单独的xType。

getX : spList -> x list
getX s = if ( s.l = [] ) then [ x ] else ... (* something is missing *)

然后我想知道什么看起来像一个更一般的情况，当l是一个非空列表。它将是一个spList列表。因此，类型为spList list到x list list的函数将对我有所帮助。这太棒了，因为我知道我可以将map从a到b的函数转换为从a list到b list的函数。

getXs : spList list -> x list list
getXs = map getX 

最后我可以完成我的功能getX

getX s = if ( s.l = [] ) 
then [x]                           (* the singleton made of x *) 
else let k = [x] in
let r = concat (getXs s.l) in (* get all the inner `x` *)
append k r 

现在可以看到[x] = append [x] (concat [])和getXs [] = []因此可以将其缩小为

getX = let k = [x] in                (* this level  *)
let r = concat (getXs s.l) in (* inner level *)
append k r                    (* the result  *)

对于您的情况，您必须弄清楚您的数组的map是什么，您将如何能够concat启用它们并append两个数组。但原理是一样的。

注意我的解很幼稚。使用递归追加通常是一个坏主意。优化getX并不困难，但又是另一步。