fold 相关问题

使用foldr在haskell中实现插入

如何在haskell中使用foldr实现插入。 我试过： 插入'' :: Ord a => a -> [a] -> [a] 插入'' e xs =foldr (\x -> \y -> if x 如何在haskell中使用foldr实现插入。 我试过： insert'' :: Ord a => a -> [a] -> [a] insert'' e xs = foldr (\x -> \y -> if x<y then x:y else y:x) [e] xs 没有骰子。 我必须在列表中插入元素 e，以便它位于大于或等于它的第一个元素之前。 示例： insert'' 2.5 [1,2,3] => [1.0,2.0,2.5,3.0] insert'' 2.5 [3,2,1] => [2.5,3.0,2.0,1.0] insert'' 2 [1,2,1] => [1,2,2,1] 在上一个示例中，第一个 2 被插入一个。 编辑： 谢谢@Lee。 我现在有这个： insert'' :: Ord a => a -> [a] -> [a] insert'' e xs = insert2 e (reverse xs) insert2 e = reverse . snd . foldr (\i (done, l) -> if (done == False) && (vj e i) then (True, e:i:l) else (done, i:l)) (False, []) where vj e i = e<=i 但是这不起作用： insert'' 2 [1,3,2,3,3] => [1,3,2,2,3,3] insert'' 2 [1,3,3,4] => [1,3,2,3,4] insert'' 2 [4,3,2,1] => [4,2,3,2,1] 解决方案： insert'' :: Ord a => a -> [a] -> [a] insert'' x xs = foldr pom poc xs False where pom y f je | je || x > y = y : f je | otherwise = x : y : f True poc True = [] poc _ = [x] 谢谢@Pedro Rodrigues（只需将 x>=y 更改为 x>y。） （如何将此标记为已回答？） 你需要 paramorphism 为此： para :: (a -> [a] -> r -> r) -> r -> [a] -> r foldr :: (a -> r -> r) -> r -> [a] -> r para c n (x : xs) = c x xs (para c n xs) foldr c n (x : xs) = c x (foldr c n xs) para _ n [] = n foldr _ n [] = n 有了它， insert v xs = para (\x xs r -> if v <= x then (v:x:xs) else (x:r)) [v] xs 我们可以用 foldr 来模仿 init . tails 的同态，如下所示：需要根据元素升序的中断将列表划分为列表（Haskell）。 因此解决方案是 import Data.List (tails) insert v xs = foldr g [v] (init $ tails xs) where g xs@(x:_) r | v <= x = v : xs | otherwise = x : r 对同态进行编码的另一种方法是通过一系列函数，如 Pedro Rodrigues 的答案中所示，安排 从左到右信息流，同时传递输入列表本身的第二个副本：一个参数（复制 tails 的效果）： insert v xs = foldr g (\ _ -> [v]) xs xs where g x r xs | v > x = x : r (tail xs) -- xs =@= (x:_) | otherwise = v : xs -- visual aid to how this works, for a list [a,b,c,d]: -- g a (g b (g c (g d (\ _ -> [v])))) [a,b,c,d] 与他的答案中的版本不同，这不会复制插入点之后的列表结构的其余部分（这是可能的，因为同态性“鱼与熊掌兼得”）。 这是我的看法： insert :: Ord a => a -> [a] -> [a] insert x xs = foldr aux initial xs False where aux y f done | done || x > y = y : f done | otherwise = x : y : f True initial True = [] initial _ = [x] 但是恕我直言，使用 foldr 并不是解决这个问题的最佳选择，对我来说以下解决方案更容易理解： insert :: Int -> [Int] -> [Int] insert x [] = [x] insert x z@(y : ys) | x <= y = x : z | otherwise = y : insert x ys 我想折叠在这里不太方便。它总是处理列表中的all元素，但是您需要在找到第一个出现的元素后停止。 当然这是可能的，但你可能不想使用这个： insert' l a = snd $ foldl (\(done, l') b -> if done then (True, l'++[b]) else if a<b then (False, l'++[b]) else (True, l'++[a,b])) (False, []) l 这是另一个使用 foldr 的解决方案。与这里的其他人相比，它简单易懂。 insert :: Ord a => a -> [a] -> [a] insert a = foldr swap [a] where swap y x_xs@(x:xs) | y > x = x:y:xs | otherwise = y:x_xs 但是，它有一个严重的限制：与使用正常递归解决方案的标准Data.List.insert不同，并且与 Pedro 和 Will Ness 的答案不同，这个版本在给定无限列表时会崩溃。 ghci> take 10 $ insert 4 [1,3..19] -- This works fine. [1,3,4,5,7,9,11,13,15,17] ghci> take 10 $ insert 4 [1,3..] -- This crashes. *** Exception: stack overflow ghci> import qualified Data.List as L (insert) ghci> take 10 $ L.insert 4 [1,3..] [1,3,4,5,7,9,11,13,15,17]

从“级联ifs”折叠表达式中检索值

假设我想使用以下语法创建自己的基于 lambda 的开关： auto s = make_switch(std::pair{0, []{ return 0; }}, std::pair{1, []{ 返回 50; }}，...

F# FoldBack 转换为尾递归函数

出于学习目的，我模拟了 List.foldBack。模拟版本是头递归的。 有没有一种优雅的方法将其转换为尾递归版本？ 让 li : int 列表 = [1;2;3] 让记录

Rust 中的欧拉项目#2

我正在学习 Rust，所以我正在做 Project Euler 问题，因为恕我直言，它们是很好的练习。 但我已经陷入了第二个问题。这个想法是找到所有偶数的总和......

用递归公式替换证明

以下问题和部分解决方案来自 Richard Bird 的 Thinking Functionly with Haskell (pp 132-133, 139) 给定 折叠 f e (x:xs) = 折叠 f (f e x) xs 折叠 f e [] = e 证明折叠（@）...

一种基于邻接对构建图邻接列表的方法，类似于 MIT 方案中的“fold”

最近自学MIT 6.5151课程时，先看了CS 61AS Unit 0作为准备。然后我按照 ps0 的要求阅读了 SICP 1 到 2.1（以及相关的讲义）（还阅读了 2.2.1 作为 CS 61A...

如何重新启用标尺中的折叠箭头

我使用vscode。 可折叠代码块过去在标尺中具有折叠/展开箭头，但现在我们有了粘性滚动条。 有没有办法重新启用标尺中的折叠箭头？

在VS Code中，如何将一段代码完全展开？

我想在 Visual Studio Code 中完全展开选定的代码。有“展开”命令，但这似乎只展开所选代码的单个级别。还有...

在 Visual Studio Code 中，如何完全展开一段代码？

我想在 Visual Studio Code 中完全展开选定的代码。有“展开”命令，但这似乎只展开所选代码的单个级别。还有“全部展开”，...

在Ocaml中使用fold_left反转列表内的元组

让 lst 成为一个包含元组的列表，我想反转每个元组（元组的顺序需要相同）。例如： [(a,b);(c,d)] -> [(b,a);(d,c)] 我知道可以用地图来完成： 列表...

使用fold_left从列表创建元组列表

如何从一个列表创建元组列表，如下所示： [1； 2； 4； 6] -> [(1, 2); (4, 6)] 我想使用函数 List.fold_left 来做到这一点，因为我目前正在尝试学习它，但不知道 h...

使用折叠命令后从数据创建变量

我的主要目标是设置从不同长度的字符串中获取的变量。每个变量必须包含字符串中的 4 位数字（即 var_1 = 数字 1-4，var_2 = 数字 5-8 等...

在 Python 中将函数应用于树的所有元素

有一个树状数据结构，其节点包含标量值（整数）、列表和字典、np.array。 我需要编写一个应用聚合函数的函数（在 Python 中）...

如何使用 Python 归约或列表理解将函数列表按顺序应用于字符串？

问题陈述 我想将函数列表 fs = [ f, g, h ] 按顺序应用于字符串 text=' abCdEf ' 像 f( g( h( 文本) ) ) 之类的东西。 这可以通过

错误：无法在初始化时将 'std::Optional<int>' 转换为 'const int'

#包括 #包括 #包括 #包括 使用命名空间 std； int main() { 常量向量 v = {1, 2, 3}; 常量整数 n =

从折叠内提前返回

我一直在尝试更多地了解 Rust 的函数式语言特性，所以我尝试采用这个函数： fn 最小长度（s：字符串）-> i32 { 如果 s.len() <= 1 { return s.len()...

foldM 与 monad 状态不进行类型检查

有关 FoldM 的现有问题（例如此处和此处）并未解决 State monad。 该文档没有指定示例，我什至无法编译一个简单的示例。 导入 Control.Monad.State.Lazy 导入

Haskell Foldr1 lambda 函数添加元组值

我一直在挠头试图弄清楚这一点。如何使用foldr1（或任何其他折叠）来获取列表中元组的总和。 例子： 列表 = [(1,2), (3,4)] 总和 = 1...

C++17 可变参数模板折叠

我不明白为什么这不起作用。了解模板和可变表达式折叠的人能否解释正在发生的事情并给出可行的解决方案？ #包括 我不明白为什么这不起作用。了解模板和可变表达式折叠的人可以解释正在发生的事情并给出可行的解决方案吗？ #include <iostream> #include <string> template <typename... Args> void print(Args... args) { std::string sep = " "; std::string end = "\n"; (std::cout << ... << sep << args) << end; } int main() { print(1, 2, 3); } 它应该打印出每个参数，参数之间有一个空格，末尾有一个换行符。如果您删除 sep <<，但打印时每个参数之间没有空格，它会起作用。 二进制折叠表达式的语法必须是以下之一： (pack op ... op init) (init op ... op pack) 你拥有的是(std::cout << ... << sep << args)，它不适合任何一种形式。您需要像 (cout << ... << pack) 这样的东西，这就是删除 sep 有效的原因。 相反，您可以折叠逗号： ((std::cout << sep << args), ...); 或使用递归： template <class A, class... Args> void print(A arg, Args... args) { std::cout << arg; if constexpr (sizeof...(Args) > 0) { std::cout << sep; print(args...); } } 这可以工作，但它会打印一个尾随空格： template <typename... Args> void print(Args... args) { std::string sep = " "; std::string end = "\n"; ((std::cout << args << sep), ...) << end; } 现场魔杖盒示例 在这种情况下，正在执行逗号运算符的折叠，从而导致如下扩展： // (pseudocode) (std::cout << args<0> << sep), (std::cout << args<1> << sep), (std::cout << args<2> << sep), ..., (std::cout << args<N> << sep), 你真正想做的是： std::string sep = " "; std::string end = "\n"; (std::cout << ... << (sep << args)) << end; 因为您希望 (sep << args) 与 std::cout 一起向左折叠。这不起作用，因为 sep << args 不知道它正在流式传输到 std::cout 或根本不知道它正在流式传输； << 仅当左侧是流时才进行流式传输。 简而言之，问题在于sep << args不明白它正在流式传输。 你的另一个问题是 lambda 不够。 我们可以解决这个问题。 template<class F> struct ostreamer_t { F f; friend std::ostream& operator<<(std::ostream& os, ostreamer_t&& self ) { self.f(os); return os; } template<class T> friend auto operator<<(ostreamer_t self, T&& t) { auto f = [g = std::move(self.f), &t](auto&& os)mutable { std::move(g)(os); os << t; }; return ostreamer_t<decltype(f)>{std::move(f)}; } }; struct do_nothing_t { template<class...Args> void operator()(Args&&...)const {} }; const ostreamer_t<do_nothing_t> ostreamer{{}}; template <typename... Args> void print(Args... args) { std::string sep = " "; std::string end = "\n"; (std::cout << ... << (ostreamer << sep << args)) << end; } 活生生的例子。 （我还使用了 sep 的文字来确保我使用右值）。 ostreamer 捕获对它是 << 的事物的引用，然后将它们转储到 << 到 ostream。 整个过程对编译器来说应该是透明的，因此一个好的优化器应该消除涉及的所有内容。 正如其他人所回答的，您正在尝试使用错误的 fold-expression 格式。 您可以通过非常简单的方式使用 lambda 助手来达到您的目的： template <typename... Args> void print(Args&&... args) { std::string sep = " "; std::string end = "\n"; auto streamSep = [&sep](const auto& arg) -> decltype(arg) { std::cout << sep; return arg; }; (std::cout << ... << streamSep(args)) << end; } 这将遵循您编写的代码中预期的行为。但是，如果您想避免第一个参数之前的 sep，您可以使用以下内容： template <typename Arg, typename... Args> void print(Arg&& arg, Args&&... args) { std::string sep = " "; std::string end = "\n"; auto streamSep = [&sep](const auto& arg) -> decltype(arg) { std::cout << sep; return arg; }; std::cout << arg; (std::cout << ... << streamSep(args)) << end; } 另一种方法是下一个： #include <iostream> template<class U, class... T> void printSpaced(const U& u, const T&... args) { using std::cout; using std::endl; ((cout << u) << ... << (cout << ' ', args)) << endl; } 这样你就不会得到前导/尾随空格 用途： printSpaced(1, 2, "Hello", 4.5f); //Output 1 2 Hello 4.5 and no trailing space 你可以尝试这样的事情 template <typename... Args> void print(Args... args) { bool first = true; auto lambda = [&](auto param) { if( !first) std::cout << ','; first= false; return param; }; ((std::cout << lambda(args)), ...); } lambda 确保分隔符仅插入在两个项目之间。 另一方面，如果你不想使用 lambda，你可以重载模板： template<typename T> void print(T item) { std::cout << item; } template<typename T, typename... Args> void print(T item, Args... args) { print(item); std::cout << ','; print(args...); } 如果您不想要前导/尾随sep: template <typename First, typename... Rest> void print(First first, Rest... rest) { std::string sep = " "; std::string end = "\n"; std::cout << first; ((std::cout << sep << rest), ...); std::cout << end; } 您需要制作 std::cout << end; 一条单独的指令来处理具有一个参数的情况。

Markdown 中的可折叠标题到 html

我们的内部 git-lab wiki 使用 Markdown。 我做了几篇文章的摘要，并想将它们发布在我们的 wiki 中，这样，如果我单击标题，它应该展开并且文本显示...