使用高阶功能和工会生成集合

发布于 2025-02-13 18:37:47 字数 262 浏览 0 评论 0原文

我正在研究过去的考试，遇到了一个问题，必须在其中编写一个名为setFunc的函数以生成一个集合，其中我在元组列表中在每个元素上应用一个函数（这是笛卡尔产品操作的结果）

首先实现了一个辅助功能以进行集合：

然后我尝试实现主要功能：

setFunc x y = f x y
setFunc (x:xs) (y:ys) = (f x y) OrdUnion (setFunc f xt ys)

将不胜感激修复SetFunc。

原文

I am studying a past exam and I came across a question where I must write a function called setFunc to generate a set where I apply a function on each element in a list of tuples (which are a result of the Cartesian product operation)

First I implemented a helper function to take the union of sets:

Then I tried to implement the main function:

setFunc x y = f x y
setFunc (x:xs) (y:ys) = (f x y) OrdUnion (setFunc f xt ys)

Help on fixing setFunc would be appreciated.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

淡紫姑娘！ 2025-02-20 18:37:47

我必须使用ordunion以某种方式不允许使用sort。
。

预计这种约束将出现在问题的正文中。

问题的核心部分是我们希望输出列表为排序（从您的示例中），但是我们被告知 nother 关于参数的订单保留属性功能。因此，我们必须接受fx y输出值将以某些不可预测的随机顺序产生。

例如，我们期望这种平等能够保持：

setFunc (*) [-7,2] [-7,3] == [-21,-14,6,49]

也就是说，最大输出值来自两个最小输入值。

因此，我们有些强迫以2个步骤解决问题：

任何顺序产生fx y输出值。
以步骤1中产生的列表的

让我们调用步骤1函数cartesianfunc 。以递归方式写入它很容易：

cartesianFunc :: Ord c => (a -> b -> c) -> [a] -> [b] -> [c]
cartesianFunc f   []   ys  =  []
cartesianFunc f (x:xs) ys  =  (map (f x) ys)  ++  (cartesianFunc f xs ys)

请注意，我们已经在类型B和C上放弃了无用的ord约束。

测试：

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
...
 λ> 
 λ> :load q13784671.hs
 [1 of 1] Compiling Main             ( q13784671.hs, interpreted )
 Ok, one module loaded.
 λ> 
 λ> cartesianFunc (*) [1,2,4] [1,3,9]
 [1,3,9,2,6,18,4,12,36]
 λ>

现在步骤2：

我们不得使用库sort函数。但是，我们必须使用函数ordunion，该将两个有序列表合并到一个较大的有序列表中。

假设我们有另一个函数，例如splithalf，可以将列表划分为两个大致相等的部分，我们可以通过以下方式获得我们自己的排序函数：

分配输入列表
recursife y/em>排序它
使用合并ordunion函数结合了我们两个分类的半部分的两半。

要拆分列表，我们可以使用熟悉的 乌龟 - 荷里算法 在每次迭代中，第一部分沿一步前进，第二部分逐步前进了两个步骤。

这给出了此代码：

ordUnion :: (Ord a) => [a] -> [a] -> [a]
ordUnion a      []     = a
ordUnion []     b      = b
ordUnion (x:xs) (y:ys) = case compare x y of
    LT -> x : ordUnion xs  (y:ys)
    EQ -> x : ordUnion xs     ys
    GT -> y : ordUnion (x:xs) ys


splitHalfTH :: [a] -> ([a],[a])
splitHalfTH xs = th xs xs
  where
    th (y:ys)  (_:_:zs)  =  let  (as,bs) = th ys zs  in  (y:as, bs)
    th ys _              =  ([],ys)


mySort :: (Ord a) => [a] -> [a]
mySort  []   =  []
mySort  [a]  =  [a]
mySort  xs   =  let  (as,bs) = splitHalfTH xs  in  ordUnion (mySort as) (mySort bs)

来提出我们的setFunc函数。

setFunc :: Ord c => (a -> b -> c) -> [a] -> [b] -> [c]
setFunc fn xs ys = mySort (cartesianFunc fn xs ys)

最后，我们可以通过组合Mysort和CartesianFunc：测试：

 λ> 
 λ> cartesianFunc (*) [1,2,4] [1,3,9]
 [1,3,9,2,6,18,4,12,36]
 λ> 
 λ> mySort $ cartesianFunc (*) [1,2,4] [1,3,9]
 [1,2,3,4,6,9,12,18,36]
 λ> 
 λ> setFunc  (*) [1,2,4] [1,3,9]
 [1,2,3,4,6,9,12,18,36]
 λ>

I must use ordUnion somehow and I am not permitted to use sort.

This sort of constraint is expected to appear within the body of the question.

A core part of the problem is that we want the output list to be sorted (from your example), but we are told nothing about possible order-preserving properties of the argument function. So we must accept that the f x y output values will be produced in some unpredictable random order.

For example, we expect this equality to hold:

setFunc (*) [-7,2] [-7,3] == [-21,-14,6,49]

that is, the maximal output value results from the two minimal input values.

Hence, we are somewhat coerced into solving the problem in 2 steps:

produce the f x y output values in whatever order
sort the list produced in step 1.

Let's call the step 1 function cartesianFunc. It is easy to write it in recursive fashion:

cartesianFunc :: Ord c => (a -> b -> c) -> [a] -> [b] -> [c]
cartesianFunc f   []   ys  =  []
cartesianFunc f (x:xs) ys  =  (map (f x) ys)  ++  (cartesianFunc f xs ys)

Note that we have dropped the useless Ord constraints on types b and c.

Testing:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
...
 λ> 
 λ> :load q13784671.hs
 [1 of 1] Compiling Main             ( q13784671.hs, interpreted )
 Ok, one module loaded.
 λ> 
 λ> cartesianFunc (*) [1,2,4] [1,3,9]
 [1,3,9,2,6,18,4,12,36]
 λ>

Now for step 2:

We may not use the library sort function. But we have to use function ordUnion, which merges two ordered lists into a bigger ordered list.

Assuming we had yet another function, say splitHalf, which could split a list into two roughly equal parts, we could obtain our own sort function by:

splitting the input list
recursively sorting its two halves
combining our two sorted halves using the merging ordUnion function.

To split a list, we can use the well-know tortoise-hare algorithm where at each iteration, the first part advances by one step and the second part advances by two steps.

This gives this code:

ordUnion :: (Ord a) => [a] -> [a] -> [a]
ordUnion a      []     = a
ordUnion []     b      = b
ordUnion (x:xs) (y:ys) = case compare x y of
    LT -> x : ordUnion xs  (y:ys)
    EQ -> x : ordUnion xs     ys
    GT -> y : ordUnion (x:xs) ys


splitHalfTH :: [a] -> ([a],[a])
splitHalfTH xs = th xs xs
  where
    th (y:ys)  (_:_:zs)  =  let  (as,bs) = th ys zs  in  (y:as, bs)
    th ys _              =  ([],ys)


mySort :: (Ord a) => [a] -> [a]
mySort  []   =  []
mySort  [a]  =  [a]
mySort  xs   =  let  (as,bs) = splitHalfTH xs  in  ordUnion (mySort as) (mySort bs)

and finally we can come up with our setFunc function by combining mySort and cartesianFunc:

setFunc :: Ord c => (a -> b -> c) -> [a] -> [b] -> [c]
setFunc fn xs ys = mySort (cartesianFunc fn xs ys)

Testing:

 λ> 
 λ> cartesianFunc (*) [1,2,4] [1,3,9]
 [1,3,9,2,6,18,4,12,36]
 λ> 
 λ> mySort $ cartesianFunc (*) [1,2,4] [1,3,9]
 [1,2,3,4,6,9,12,18,36]
 λ> 
 λ> setFunc  (*) [1,2,4] [1,3,9]
 [1,2,3,4,6,9,12,18,36]
 λ>

回复收藏 0 原文

~没有更多了~