3

我有一个 Haskell 程序，它将文件作为输入并将其转换为二叉搜索树。

import System.IO    

data Tree a = EmptyBST | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

ins :: Ord a => a -> (Tree a) -> (Tree a)
ins a EmptyBST                  = Node a EmptyBST EmptyBST
ins a (Node p left right)
    | a < p                             = Node p (ins a left) right
    | a > p                             = Node p left (ins a right)
    | otherwise                             = Node p left right



lstToTree :: Ord a => [a] -> (Tree a)
lstToTree                   = foldr ins EmptyBST

fileRead                    = do    file    <- readFile "tree.txt"
                            let a = lstToTree (conv (words file))
                            return a

conv :: [String] -> [Int]
conv                        = map read

但是，当我运行以下命令时：

ins 5 fileRead

我收到以下错误：

<interactive>:2:7:
    Couldn't match expected type `Tree a0'
                with actual type `IO (Tree Int)'
    In the second argument of `ins', namely `fileRead'
    In the expression: ins 5 fileRead
    In an equation for `it': it = ins 5 fileRead

请问有人可以帮助我吗？

谢谢

4

2 回答 2

7

如果您提供fileRead类型签名，您将能够立即看到问题。让我们找出 GHC 将在内部分配给的类型注释fileRead：

fileRead = do file <- readFile "tree.txt"
              let t = lstToTree $ map read $ words file
              return t

lstToTree :: Ord a => [a] -> Tree a，并且read总是返回类型类的成员Read。所以t :: (Read a, Ord a) => Tree a。具体类型取决于文件的内容。

return将其参数包装在一个 monadreturn t中， type也是如此Ord a, Read a => IO (Tree a)。由于return t是do块中的最后一条语句，它成为 的返回类型fileRead，所以

fileRead :: (Read a, Ord a) => IO (Tree a)

所以fileRead是 aTree包裹在a 中IO，你不能直接将它传递给它，ins因为它Tree自己需要 a 。您不能从 中Tree取出IO，但可以将功能“提升”ins到IOmonad 中。

Control.Monad 导出liftM :: Monad m => (a -> r) -> (m a -> m r)。它接受一个常规函数，并将其转换为作用于诸如IO. fmap它实际上是（在标准 Prelude 中）的同义词，因为所有单子都是函子。因此，这段代码大致相当于@us202 的代码，它获取fileRead, inserts的结果5，并返回包装在IO.

liftM (ins 5) fileRead
-- or --
fmap (ins 5) fileRead

我会推荐这个fmap版本。这段代码只利用IO了函子这一事实，因此 usingliftM向读者暗示您可能也需要它是一个 monad。

“提升”是对包裹在单子或函子中的值使用纯函数的一般技术。如果你不熟悉提升（或者如果你对一般的 monad 和 functors 感到困惑），我衷心推荐Learn You A Haskell的第 11-13 章。

PS。请注意，最后两行fileRead可能应该合并，因为return实际上并没有做任何事情：

fileRead :: (Read a, Ord a) => IO (Tree a)
fileRead = do file <- readFile "tree.txt"
           return $ lstToTree $ map read $ words file

或者，由于它是一个足够短的函数，您可以完全取消do符号并fmap再次使用：

fileRead :: (Read a, Ord a) => IO (Tree a)
fileRead = fmap (lstToTree . map read . words) (readFile "tree.txt")

编辑以回应您的评论：

Haskell特意设计为将执行 IO 的代码与常规代码分开。这有一个很好的哲学原因：大多数 Haskell 函数是“纯的”——也就是说，它们的输出仅取决于输入，就像数学中的函数一样。你可以运行一个纯函数一百万次，你总是会得到相同的结果。我们喜欢纯函数，因为它们不会意外破坏程序的其他部分，它们允许惰性，并且它们允许编译器积极地为您优化代码。

当然，在现实世界中，我们需要一点杂质。像这样的 IO 代码getLine不可能是纯的（而且不做 IO 的程序是没用的！）。结果getLine取决于用户键入的内容：您可以运行getLine一百万次并每次获得不同的字符串。Haskell 利用类型系统用 type 标记不纯的代码IO。

这是问题的症结所在：如果你对不纯的数据使用纯函数，那么结果仍然是不纯的，因为结果取决于用户做了什么。所以整个计算属于IO单子。当你想引入一个纯函数IO时，你必须显式地（使用fmap）或隐式地（使用do符号）来提升它。

这是 Haskell 中非常常见的模式 - 看看我fileRead上面的版本。我曾经使用纯函数fmap对不纯数据进行操作。IO

于 2013-03-26T17:03:46.533 回答
3

您无法真正逃脱 IO monad（通过不安全函数除外），但在您的情况下实际上不需要这样做：

main = do f <- fileRead
          let newtree = ins 5 f
          putStr $ show newtree

（现场演示：这里）

于 2013-03-26T16:08:42.713 回答