1

我有一个在运行时从文件中读取并以元组表示的数据列表，如下所示：

[(1,0.1),(2,0.2),(3,0.3)...etc...]

我写了一个函数，它接受一个列表和两个整数作为参数并返回一个双精度数：

f :: [(Int,Double)] -> Int -> Int -> Double
f mylist i j
    | j < n = (do some stuff)
    | otherwise = max (f mylist (i-1) j) (some other stuff with m_i and p_i)
    where m_i = fst $ mylist !! (i-1)
          p_i = snd $ mylist !! (i-1)

现在，我是 Haskell 和纯函数概念的新手，但由于列表是静态的（它不会改变），我想知道是否真的需要将列表传递给函数？

通过无数层递归传递大列表是不好的做法吗？

鉴于我在运行时阅读了列表，我可以“设置”两个函数m并p像这样使用它们吗？

f :: Int -> Int -> Double
f i j
    | j < n = (do some stuff)
    | otherwise = max (f (i-1) j) (some other stuff with m_i and p_i)
    where m_i = m (i-1)
          p_i = p (i-1)

如果是这样，我如何设置mandp函数（它们是纯的，对吗？）以基本上返回我在运行时从文件中读取的值（如果我理解正确，这是不纯的）。

谢谢你的帮助！

4

5 回答 5

4

尽管有一些陷阱，但在大列表上递归并不是一个非常糟糕的做法。一般来说，只要你的递归函数是递增的，你就可以了（O(1) memory, O(n) time）即使是非常大的列表。

在您的情况下，您似乎正在向后阅读列表，因为您的索引值向下递归。这意味着您必须将整个列表加载到内存中才能反转它——也许最好存储反转的列表？

如果你从一个文件中读取，你几乎肯定是不纯的。在某些情况下，假装它是一个纯粹的操作可能很有价值，但通常最好将这些东西传递给基于 IO 的早期设置/配置步骤。

例如，我的可执行文件可能看起来像这样

main :: IO ()
main = do bigList <- readFileSomehow -- this is impure
          let res = f bigList        -- this is pure
          print res                  -- this is impure again

在这里，我们使用do语法bigList :: [(Int, Double)]从读取的不纯文件中提取作为第一步。然后我们立即将其传递bigList给纯函数f并获得纯结果res。最后，我们在 pure 上运行不纯print动作res。

这让我们可以将main函数中的所有杂质隔离开来，并f完全独立于琐碎的不纯细节（例如“如何”我们一开始就达到如此大的输入）进行编写。

m可以使用您描述的和p函数进一步抽象此列表的概念。他们所做的只是隐藏列表并只允许通过(!!).

inner :: Int -> Int -> (Int -> Int) -> (Int -> Double) -> Something

outer :: [(Int, Double)] -> Int -> Int -> Something
outer bigList i j = inner i j (\ix -> fst $ bigList !! ix) (\ix -> snd $ bigList !! ix)

outer现在“包装”在哪里，除了通过这两个索引功能外，inner它无法看到。bigList

最后，不幸的是，整个方法并没有一种非常“Haskelly”的感觉。在大列表上使用显式递归(!!)往往会导致速度减慢和代码重复。如果可能的话，尝试用maps 和s 来表达你的意图几乎总是一个更好的主意。foldr

于 2013-09-25T19:37:46.853 回答
3

通过无数层递归传递大列表是不好的做法吗？

从概念上讲，您似乎担心复制大列表，但事实并非如此，Haskell 将通过递归处理相同的数据结构。您无需明确将其取出。

使用显式(!!)可能会导致一些问题，其中至少是因为它的部分功能。由于您正在对数据进行线性扫描，因此可能值得花时间尝试将您的问题表述为地图或折叠，或它们的某种组合。如果你能做到这一点，你就会对编译器进行很多优化。

也强烈建议查看vector图书馆。

http://hackage.haskell.org/package/vector-0.10.0.1

于 2013-09-25T19:34:50.210 回答
1

简而言之，没有。

如果您正在从文件中读取列表，那么它将不是纯的，并且如果不将其传递给纯函数，就无法从纯函数中使用它。

从文件中读取列表意味着读取和解析它的结果是IO [(Int,Double)]. 您不能从 IO 中“提取”值；只能将纯函数引入 IO，例如使用fmapor bind。

为了显示：

main = do
         ...
         xs <- readFile -- this is IO String
         let mylist = parse xs -- whatever conversion
                               -- from String to [(Int,Double)]
         -- mylist cannot live outside this IO
         let zs = f mylist i j -- so got to pass it to f
         ...
于 2013-09-25T19:34:07.633 回答
1

是的，您的列表是不可变的，但在编译时并不知道。所以你有两个选择

  1. 通过名单
  2. 传递一个知道此列表的函数，并将在索引处为您提供它的值

请注意，这些在概念上是等效的，都涉及您传递一些数据来表示值列表，这只是您如何表示它的问题。

所以p看起来m像

 myList = ...
 p i = fst $ myList !! i
 m i = fst $ myList !! i

这真的不会让你买多少。

如果它让您感觉更好，则将 10000 个元素的列表传递给函数（而不是创建）的成本与 3 的列表相同。它编译为 head + 指向其余元素的指针或 nil 值。这是因为 Haskell 有单链表，

List a = Cons a (List a) -- Head, rest of list
       | Nil             -- End of list

因此，按值传递它与命令式数组相比非常便宜，但查找时间相应地受到影响。

作为这个的必然结果，要非常小心(!!)。考虑您的问题是否更好地表述为折叠或地图。使用高阶组合器非常Haskelly :)

于 2013-09-25T19:34:43.860 回答
1

如何每 1 个列表使用 2 个函数 - 使用map和制作，例如，一个元组

result :: (a->b) -> (a->c) -> [a] -> [(b,c)]
result m p = map (\elem -> (f elem , p elem) )  list

如果您将列表作为参数传递 - 没什么不好。如果您不使用它 - 编译器将不会读取它。但是算法的复杂性很重要。

于 2013-09-25T19:37:16.053 回答