Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
236 views
in Technique[技术] by (71.8m points)

list - How to interpret a Traversable type as an Applicative in this function?


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The intuition for the list applicative is that of nondeterministic computation. You can think of a list of type [X] with n elements as being a calculation that produces an X, and it's definitely one of the n choices of X contained in that list, but any of them is possible.

For example, the list ['a','e'] represents a calculation that could produce 'a' or could produce 'e'. The list [-4,4] might be the result of asking about the square root of 16. The list [] is a nondeterministic calculation that can't correctly produce any value! (Say, the result of asking about the real square root of -16...)

In this interpretation, when we have a list of functions fs and some values xs, the list fs <*> xs is the list of all the possible results you could get by applying any of the functions in fs to any of the arguments in xs. Meanwhile, the list pure x is the deterministic calculation that always produces exactly one result, namely, x.

So! If you have a nested list, then there are various alternative ways of thinking about what it means, including that it is a list of nondeterministic calculations or that it is a nondeterministic calculation that produces lists as its result. The sequenceA function transports you between these representations: it takes a list of nondeterministic calculations and produces a single nondeterministic calculation whose result is a list. So:

 [[a,b,c],[d,e],[f,g,h,i]]

You can think of this as a list with three elements. The first is a choice between a, b, and c, the second is a choice between d and e, and the third is a choice between f, g, h, and i. The sequenceA function will produce a nondeterministic choice of lists, each of which has the same shape as the outer list above; that is, each list we are choosing between will have length 3. The first element will come from [a,b,c]; the second will come from [d,e], and the third from [f,g,h,i]. If you think for a bit about all the ways that could happen, you will see it's exactly their Cartesian product!


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...