如何在不知道密钥的情况下从 F# Map 获取第一个键值对？

Question

如何在不知道密钥的情况下从 F# Map 获取第一个 key,value pair？

我知道 Map 类型用于在给定键的情况下获取相应的值，例如find.

我也知道可以将地图转换为列表并使用 List.Head，例如

List.head (Map.toList map)

我愿意这样做
1.没有钥匙
2.不知道key和value的类型
3. 不使用可变
4. 无需遍历整个地图
5. 不进行遍历整个地图的转换，例如Map.toList，等等

我也知道，如果有人获得第一个 key,value pair 它可能没有用，因为地图文档没有说明在两个不同的调用中使用地图是否保证相同的顺序。

如果无法编写代码，则可以接受来自 MSDN 等站点的现有参考资料，解释并说明为什么不能编写。

TLDR;

我如何解决这个问题是转换这个函数：

let findmin l = 
    List.foldBack
        (fun (_,pr1 as p1) (_,pr2 as p2) -> if pr1 <= pr2 then p1 else p2)
        (List.tail l) (List.head l)

基于list，用于查找string * int的关联列表中的最小值。

示例列表：

["+",10; "-",10; "*",20; "/",20]

该列表用于解析具有优先级的二元运算符表达式，其中string是二元运算符，int是优先级。其他函数是在数据上执行的，因此使用 F# map 可能比 list 更有优势。我还没有决定最终的解决方案，但想在 map 还处于最前沿时探索这个问题。

目前我正在使用：

let findmin m =
    if Map.isEmpty m then 
        None
    else
        let result = 
            Map.foldBack 
                (fun key value (k,v) -> 
                    if value <= v then (key,value) 
                    else (k,v))
                m ("",1000)
        Some(result)

但在这里我不得不在初始状态 ("",1000) 中进行硬编码，而更好的做法是仅使用地图中的第一个值作为初始状态，然后将地图的其余部分作为起始值传递地图与列表相同：

(List.tail l) (List.head l)

是的，这是对地图进行分区，但是没有用，例如，

let infixes = ["+",10; "-",10; "*",20; "/",20]
let infixMap = infixes |> Map.ofList
let mutable test = true
let fx k v : bool =
    if test then 
        printfn "first"
        test <- false
        true
    else 
        printfn "rest"
        false
let (first,rest) = Map.partition fx infixMap

这导致

val rest : Map<string,int> = map [("*", 20); ("+", 10); ("-", 10)]  
val first : Map<string,int> = map [("/", 20)]

这是两个映射，而不是第一个的键值对

("/",20)

关于答案的注释

出于优先解析的实际目的，在最终转换中看到 - 之前的 + 操作是可取的，因此 returning + 在 [=25] 之前=] 是可取的。因此

的答案变体

let findmin (map : Map<_,_>) = map |> Seq.minBy (fun kvp -> kvp.Value)

通过

实现了这一点并实现了这一变化

let findmin m = 
    Map.foldBack (fun k2 v2 st ->
        match st with
        | Some(k1, v1) when v1 < v2 -> st
        | _ -> Some(k2, v2)) m None

Seq.head 的使用 return map 中的第一项，但必须注意 map 是使用排序的键构建的，而对于我的实际示例我想从最低值 10 开始，因为项目按 key 排序，第一个 returned 是 ("*",20) 和 * 是第一个键，因为键是字符串并按这样排序。

为了实际使用的答案，我必须在调用之前检查一个空列表，并使用 KeyValuePair 将输出按摩到一个元组中 let (a,b) = kvp.Key,kvp.Value

Answer 1

Map 实现了 IEnumerable<KeyValuePair<_,_>>，因此您可以将其视为 Seq，例如：

let findmin (map : Map<_,_>) = map |> Seq.minBy (fun kvp -> kvp.Key)

Answer 2

我认为没有一个答案可以完全满足您的所有要求，但是：

您可以使用 m |> Seq.head 访问第一个键值对。与将地图转换为列表不同，这是惰性的。这并不能保证您始终获得相同的第一个元素，但实际上，实现将保证这一点（尽管它可能会在下一个版本中改变）。
为了找到最小值，您实际上不需要保证 Seq.head returns 总是相同的元素。它只需要给你一些元素。
您可以使用其他基于 Seq 的函数，正如@marklam 在他的回答中提到的那样。
你也可以使用 fold 和 option<'K * 'V> 类型的状态，你可以用 None 初始化它，然后你就不用担心找不到第一个元素：
```
m |> Map.fold (fun st k2 v2 ->
    match st with
    | Some(k1, v1) when v1 < v2 -> st
    | _ -> Some(k2, v2)) None
```

Answer 3

它比其他答案更简单。 Map 内部使用 AVL 平衡树，因此条目已经按键排序。正如@marklam 所提到的 Map 实现 IEnumerable<KeyValuePair<_,_>> 所以：

let m = Map.empty.Add("Y", 2).Add("X", 1)
let (key, value) = m |> Seq.head
// will return ("X", 1)

无论元素添加到地图的顺序如何，Seq.head 可以直接在地图上操作，return key/value 最小键的映射。

有时需要将 Map 显式转换为 Seq:

let m = Map.empty.Add("Y", 2).Add("X", 1)
let (key, value) = m |> Map.toSeq |> Seq.head

我看到的这个案例的错误消息是 "the type 'a * 'b does not match the type Collections.Generic.KeyValuePair<string, int>"。也可以添加类型注释而不是 Map.toSeq.

如何在不知道密钥的情况下从 F# Map 获取第一个键值对？

How does one get the first key,value pair from F# Map without knowing the key?

f#

dictionary

key-value

关于答案的注释