Bob*_*Bob 19 f# data-structures
我正在尝试学习F#并且在看到一些奇怪的东西(至少对我来说)时正在观看视频.有问题的视频在这里,相关部分从2:30开始,感兴趣的人.但基本上,这个人说F#使得使用数组变得很尴尬,并且设计师故意这样做,因为列表更容易"预先添加和追加".
立即浮现在脑海中的问题:在不可改变的语言中添加和追加一些应该不赞成的东西并不容易吗？具体来说,我正在考虑C#的列表,您可以在其中执行类似的操作List.Add(obj);并改变列表.使用数组,您必须创建一个全新的数组,但这也是在不可变语言中需要发生的事情.
那么为什么F#的设计师更喜欢列表呢？列表和数组之间的不可变环境的根本区别是什么？我错过了什么？F#中的列表真的是链接列表吗？
Ste*_*sen 51
我不同意"F#使得使用数组变得尴尬".实际上,与大多数语言相比,F#使得使用数组非常好.
例如,F#具有文字数组结构:let arr = [|1;2;3;4;|].在阵列上甚至可能更酷,模式匹配:
match arr with
| [|1;2;_;_|] -> printfn "Starts with 1;2"
| [|_;_;3;4|] -> printfn "Ends with 3;4"
| _ -> printfn "Array not recognized"
至于为何不可变单向链表像F#函数式编程是首选,有很多的说法,但是简单的答案是,它允许一个O(1)前置效率,并允许共享节点的实现,所以很容易在记忆.例如,
let x = [2;3]
let y = 1::x
这里y是通过在x之前加1来创建的,但是x既没有修改也没有复制,所以y非常便宜.我们可以看到这有多可能,因为x指向最初构造的列表的头部2,并且只能向前移动,并且因为它指向的列表的元素不能被突变,所以它不会与y共享节点的问题.
Tom*_*cek 13
首先,数组是非常低级的数据结构,只有在创建数组时才知道数组的长度,它们才真正有用.通常情况并非如此,这就是C#程序员使用System.Collections.Generic.List<T>和F#程序员使用F#的原因list<T>.
F#更喜欢自己的功能列表而不是使用.NET的原因List<T>是函数式语言更喜欢不可变类型.list.Add(x)您可以通过编写创建包含添加到前端的项目的新列表,而不是通过调用来修改对象let newList = x::list.
我也同意斯蒂芬在F#中使用数组并不尴尬.如果您知道正在使用的元素数量或者您正在转换某些现有数据源,那么使用数组非常简单:
/ You can create arrays using `init`
let a = Array.init 10 (fun i -> (* calculate i-th element here *) )
// You can transform arrays using `map` and `filter`
a |> Array.map (fun n -> n + 10)
|> Array.filter (fun n -> n > 12)
// You can use array comprehensions:
let a2 = [| for n in a do
if n > 12 then yield n + 10 |]
这与处理列表基本相同 - 您可以使用列表推导[ ... ]和列表处理功能List.map等.差异确实出现在初始化列表/数组时.
F#使得使用数组变得尴尬
F#提供了许多功能,使得使用数组比使用其他语言更容易,包括数组文字,数组模式和高阶函数.
立即浮现在脑海中的问题:在不可改变的语言中添加和追加一些应该不赞成的东西并不容易吗？
我相信你误解了这个陈述的含义.当人们谈论在纯功能数据结构的上下文中进行前置和附加时,他们指的是创建一个新集合,该集合是使用现有集合派生(并与其大部分内部共享).
那么为什么F#的设计师更喜欢列表呢？
F#从OCaml继承了一些与列表相关的功能,它们继承了标准ML和ML,因为单链接的不可变列表在其应用程序域(元编程)的上下文中非常有用,但我不会说F#的设计者更喜欢列表.
列表和数组之间的不可变环境的根本区别是什么？
在F#中,列表提供O(1)前置和附加以及O(n)随机访问,而阵列提供O(n)前置和附加以及O(1)随机访问.数组可以变异但列表不能变异.
我错过了什么？
纯功能数据结构的基础知识.读冈崎.
F#中的列表真的是链接列表吗？
是.具体来说,单链接的不可变列表.实际上,在某些ML中,list类型可以定义为:
type 'a list =
| ([])
| (::) of 'a * 'a list
这就是为什么::操作符是构造函数而不是函数的原因,所以你不能用(::)它来编写,例如(+).
F#列表更像是以下数据结构 - 单个链表:
public class List<T> {
public List(T item, List<T> prev) { /*...*/ }
public T Item { get; }
public List<T> Prev { get; }
}
因此,当创建新列表时,它实际上创建了一个单个节点,其中引用了前一个列表的第一个元素,而不是复制整个数组.