问题[haskell](coding)

例如，考虑这个函数，它可以在 WM 中使用，允许在给定的显示器上将窗口从一个桌面移动到另一个桌面，

moveWindowSTM :: Display -> Window -> Desktop -> Desktop -> STM ()
moveWindowSTM disp win a b = do
  wa <- readTVar ma
  wb <- readTVar mb
  writeTVar ma (Set.delete win wa)
  writeTVar mb (Set.insert win wb)
 where
  ma = disp ! a
  mb = disp ! b

显然还有它的IO包装，

moveWindow :: Display -> Window -> Desktop -> Desktop -> IO ()
moveWindow disp win a b = atomically $ moveWindowSTM disp win a b

然后假设

• 我们的交易在第三次尝试时成功了，
• ma因为在第一次尝试时，它会因另一个并发事务提交而失效，该事务在我们的事务之后立即更改了内部的值wa <- readTVar ma，
• 而在第二次尝试时，它被另一个并发事务无效，该事务开始提交并更改了我们的事务中的一个或ma两个的内容。mbwriteTVar ma (Set.delete win wa)

在这种情况下，交易日志将如何演变，以及验证在什么时候会失败？

Simon Marlow 所著《Haskell 中的并行和并发编程》的相关摘录如下（但 Simon Peyton Jones 所著的论文《美丽的并发性》中也提供了类似的信息）：

STM 事务的工作原理是累积事务期间迄今为止发生的操作的日志。日志有三种readTVar用途：writeTVar

• 通过将writeTVar操作存储在日志中而不是立即将其应用到主内存中，丢弃事务的影响很容易；我们只需丢弃日志即可。因此，中止事务的代价很小且固定。

• 每个人都readTVar必须遍历日志来检查 是否是TVar由之前的 写入的writeTVar。因此，readTVar是日志长度上的 O(n) 操作。

• 因为日志包含所有操作的记录readTVar，所以可以使用它来发现事务期间的完整TVars读取集，我们需要知道这些才能实现retry。

当事务结束时，STM 实现会将日志与内存内容进行比较。如果当前内存内容与 读取的值匹配readTVar，则将事务的结果提交到内存；如果不匹配，则丢弃日志并从头开始重新运行事务。此过程以原子方式进行，方法是在TVars事务执行期间锁定所有涉及的 。GHC 中的 STM 实现不使用全局锁；TVars提交期间仅锁定涉及事务的 ，因此对不相交的 集合进行操作的事务TVars可以不受干扰地继续进行。

在 Simon Marlow 所著的《Haskell 中的并行和并发编程》中，第 7 章从第 125 页开始，其中有这样一个例子：

import Control.Concurrent
import Control.Monad
import System.IO

main :: IO ()
main = do
  hSetBuffering stdout NoBuffering
  _ <- forkIO (replicateM_ 100000 (putChar 'A'))
  replicateM_ 100000 (putChar 'B')

其输出如下

BBBBBBBABABABAAAAAAA

100000（顺便说一下，这是我在上面的代码片段中更改10并运行程序时真正得到的输出）。

在本章末尾，第 140 页，有如下评论（我强调）：

[…] 这是公平性保证在实践中的一个例子。[…]。因此，这会导致两个线程之间完美地交替。交替模式被打破的唯一情况是，当一个线程没有持有 时，它被取消调度MVar。事实上，由于抢占，这种情况确实会不时发生，我们偶尔会在输出中看到一个由单个字母组成的长字符串。

MVar根据我给出的输出，是的，我可以看到交替被破坏了，但我不太理解上面的解释。第一个例子中甚至没有。

在Simon Marlow 所著的《Haskell 中的并行和并发编程》第 133 和 134 页中显示了以下代码：

type Name        = String
type PhoneNumber = String
type PhoneBook   = Map Name PhoneNumber

newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  return (Map.lookup name book)

下一页有一些观察。不过，第二段的最后部分让我有点困惑。以下是该段的前半部分：

在可变包装器中使用不可变数据结构还有其他好处。需要注意的是，在lookup操作中，我们只是获取了状态的当前值，然后复杂的操作在/序列Map.lookup之外进行。这对于并发性来说非常有利，因为这意味着锁只会被持有很短的时间。takeMVarputMVar

这对我来说相当清楚，因为我理解 会takeMVar锁定，然后putMVar立即释放，这样后续对 的并发访问PhoneBookState就不会再受到任何阻碍。同时，我还发现 可能会发生进一步的变异，所以当 以 为返回值MVar时，该对可能已经从映射中移除（或者，如果返回，则可能已经将一些对添加到映射中）。lookupJust smth(name, smth)Nothing(name, smth)

然而，我不明白该段接下来的部分想要表达什么：

这之所以可能，是因为状态的值是不可变的。如果数据结构是可变的，那么我们在操作它时就必须持有锁。⁵

---

⁵. 另一种选择是使用无锁算法，但这非常复杂，很难做到正确。

这是什么意思？作者指的是将某些 API 暴露给 mutated 的情况Map吗？除非我们在 中，否则这根本不可能，IO对吧？或者他指的是对 的内容执行的修改（由释放锁m后的其他线程执行）会以某种方式影响 的内容？putMVarbook

我找不到此行为的文档，它看起来像是一个错误（[编辑] 确实是：gitlab.haskell.org/ghc/ghc /-/issues/10387）。我遗漏了什么吗？

在 GHCi 中：

    > import GHC.Real
    > inf = 1/O :: Double

    > inf
    Infinity

    > infinity
    1 % 0

    > fromRational infinity
    Infinity

    > toRational inf
    179769313486231590... % 1
    
    > toRational inf == infinity 
    False

[编辑 ： ]

有一个解决方法。使用包ieee754，可以定义以下内容：

import GHC.Real
import qualified Numeric.IEEE as IEEE

toRational' :: (IEEE.IEEE a, Real a) => a -> Rational
toRational' a
  | a == IEEE.infinity = infinity
  | a == -IEEE.infinity = -infinity
  | otherwise = toRational a

data Zero = Zero 
data Succ x = Succ x 

class NatToPeano a b | a -> b where 
    toPean :: b
instance NatToPeano 0 Zero where toPean = Zero 
instance (NatToPeano (x-1) a) => NatToPeano x (Succ a) where
     toPean = Succ (toPean @(x-1))

这会产生错误：

 Functional dependencies conflict between instance declarations:
  instance NatToPeano 0 Zero -- Defined at parsejava.hs:26:10
  instance NatToPeano (x - 1) a => NatToPeano x (Succ a)
    -- Defined at parsejava.hs:28:10

 26 | instance NatToPeano 0 Zero where

使用 Haskellcrypton包，我尝试生成相同的输出，openssl dgst但不知道哪里出错了。请帮忙。

openssl dgst：

$ echo "TheMessage" | openssl dgst -sha256 -mac HMAC -macopt key:"TheKey"
SHA2-256(stdin)= 7b2e5669f4a5fa30a3fa0e9147f8975883cddff77725c99a6db07395b9665974

加密：

ghci> hmacGetDigest ( hmac ("TheKey" :: ByteString) ("TheMessage" :: ByteString) :: HMAC SHA256 )
39c17c48adbc2ea4d469af9ecb2569f921053843af2a0a7716b7a180b0cedff6

谢谢。

我读到变量在 haskell 中是不可变的，并且类似下面的内容在 haskell 中不起作用。

x = 30
x = x+1

但我仍然尝试这样做，看看编译器返回了什么，我得到了以下结果：

编译器变得无响应并且不执行任何操作，直到我按下 ctrl+c 并中断它。

为什么会发生这种情况？为什么编译器变得无响应而不是返回某种错误？

我正在使用 Haskell 实现的生成器来完成家庭作业。我有一个andAlso函数应该为生成器添加一个额外的谓词，但它在所有测试用例中都无法正常工作。虽然它看起来是正确的

这是我的生成器类型定义：

-- Type definition for a generator: a function producing a sequence of values
-- 1. The first function generates the next value.
-- 2. The second function checks if generation should continue.
-- 3. The third value is the initial value, or seed. It does not count as being generated by the generator.
type Generator a = (a -> a, a -> Bool, a)

我目前的实现andAlso：

-- Adds an additional predicate to a generator.
andAlso :: (a -> Bool) -> Generator a -> Generator a
andAlso p (f, g, s) = (f, \x -> g x && p x, s)

我正在使用辅助函数takeGen来可视化测试结果：

takeGen :: Int -> ((a -> a), (a -> Bool), a) -> [a]
takeGen 0 _ = []
takeGen n (next, pred, seed)
  | not (pred seed) = []
  | otherwise = seed : takeGen (n-1) (next, pred, next seed)

测试用例和结果

以下是我的测试用例及其结果：

-- Test 1: Filter for odd numbers
takeGen 10 (andAlso (\x -> x `mod` 2 == 1) ((+1), (<10), 0))
-- Expected: [1,3,5,7,9], but getting: [1]

-- Test 2: Filter for numbers divisible by 3
takeGen 10 (andAlso (\x -> x `mod` 3 == 0) ((+1), (<10), 0))
-- Expected: [0,3,6,9], but getting: [0]

-- Test 3: Filter for numbers greater than 5
takeGen 10 (andAlso (>5) ((+1), (<10), 0))
-- Works correctly: [6,7,8,9]

-- Test 4: Combine two additional predicates
takeGen 10 (andAlso (>3) (andAlso (<8) ((+1), (<10), 0)))
-- Works correctly: [4,5,6,7]

-- Test 5: Test with a different generator function
takeGen 10 (andAlso (<15) ((+2), (<20), 1))
-- Works correctly: [1,3,5,7,9,11,13]

takeGen 10 (andAlso (<10) ((+1), (<10), 0))
-- Works correctly: [0,1,2,3,4,5,6,7,8,9]

我尝试过的方法

我尝试过的各种实现andAlso，包括：

1. 当前实现如上所示
2. 调整谓词在序列中的应用方式
3. 尝试找到满足两个谓词的第一个有效值

一些测试用例运行正常，但其他测试用例（特别是测试 1 和 2）并未返回所有预期值。

我的问题

我的实现有什么问题andAlso？我应该如何修复它才能使所有测试用例按预期工作？问题在于生成器的定义方式、takeGen工作原理，还是andAlso附加谓词的应用方式？

其他背景信息

我已经实现的其他与生成器相关的功能：

nthGen :: Integer -> Generator a -> a
nextGen :: Generator a -> Generator a
lengthGen :: Generator a -> Integer
hasLengthOfAtLeast :: Integer -> Generator a -> Bool
constGen :: a -> Generator a
foreverGen :: (a -> a) -> a -> Generator a
emptyGen :: Generator a

感谢您帮助我了解我的实施出了什么问题。

绝对最小的解析库可能是：

{- | Input error type. -}
data InputError = InputError
    deriving (Eq, Show)

instance Semigroup InputError where
    (<>) _ _ = InputError

instance Monoid InputError where
    mempty = InputError


{- | The parsing monad. -}
newtype Parser s e a = Parser ([s] -> Either e (a, [s]))
    deriving stock Functor


-- Instances.
instance Applicative (Parser s e) where
    pure x = Parser $ \ xs -> pure (x, xs)

    (<*>) p q = Parser $ \ xs -> do
        (f, ys) <- run p xs
        (x, zs) <- run q ys
        pure (f x, zs)

instance Monad (Parser s e) where
    (>>=) p h = Parser $ \ xs -> do
        (x, ys) <- run p xs
        run (h x) ys

instance Monoid e => Alternative (Parser s e) where
    empty = Parser $ \ _ -> Left mempty

    (<|>) p q = Parser $ \ xs ->
        case run p xs of
            r1@(Right _) -> r1
            Left e1      ->
                case run q xs of
                    r2@(Right _) -> r2
                    Left e2      -> Left $ e1 <> e2

{- | Primitive parser getting one element out of the stream. -}
one :: Parser s InputError s
one = Parser $ \ xs ->
    case uncons xs of
        Nothing -> Left InputError
        Just p  -> Right p

{- | Run the parser on input and return the results. -}
run :: Parser s e a -> [s] -> Either e (a, [s])
run (Parser p) = p

编译（使用 GHC2021 语言；必须添加一些导入）。在 cabal repl 中的 ghci 中加载它：

ghci> let p = take 2 <$> many one
ghci> run p "0123"
Right ("01","")

这意味着解析器已经使用了所有的输入——我期望看到的是Right ("01", "23")。

所以我的问题是：懒惰在哪里“中断”，可以这么说，有什么办法可以恢复它吗？我说的“恢复它”是指以不同的方式执行实例实现，这样它就many和预期的一样懒惰，因为如果我添加

{- | Implement lazy 'many' -}
atMostN :: Monoid e => Word -> Parser s e a -> Parser s e [a]
atMostN n p = go n
    where
        go 0 = pure []
        go m = do
            r <- optional p
            case r of
                Nothing -> pure []
                Just x  -> (x: ) <$> go (pred m)

并将其加载到 ghci 中，我得到了预期的结果：

ghci> let q = atMostN 2 one
ghci> run q "0123"
Right ("01","23")

以下是《Learn You a Haskell》第 13 章中状态单子的定义

instance Monad (State s) where
    return x = State $ \s -> (x,s)
    (State h) >>= f = State $ \s -> let (a, newState) = h s
                                        (State g) = f a
                                    in  g newState

根据此定义，在我看来，虽然返回的是较新的版本，但tuple 中的状态f a似乎将被 替换。以Real World Haskell第 10 章中的具体示例为例，这显然不是作者的本意（请注意使用而不是 ，因为他们尚未正式引入 monad）newState ==>>>=

parseByte :: Parse Word8
parseByte =
    getState ==> \initState ->
    case L.uncons (string initState) of
      Nothing ->
          bail "no more input"
      Just (byte,remainder) ->
          putState newState ==> \_ ->
          identity byte
        where newState = initState { string = remainder,
                                     offset = newOffset }
              newOffset = offset initState + 1

在哪里

newtype Parse a = Parse {
      runParse :: ParseState -> Either String (a, ParseState)
    }

identity :: a -> Parse a
identity a = Parse (\s -> Right (a, s))
 
(==>) :: Parse a -> (a -> Parse b) -> Parse b
firstParser ==> secondParser  =  Parse chainedParser
  where chainedParser initState   =
          case runParse firstParser initState of
            Left errMessage ->
                Left errMessage
            Right (firstResult, newState) ->
                runParse (secondParser firstResult) newState

在parseByte，我不明白如何initState不取代newState。