Perguntas[haskell](coding)

Por exemplo, considere esta função, que poderia ser usada em um WM para permitir mover uma janela de uma área de trabalho para outra em uma determinada tela,

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

e obviamente seu IOinvólucro,

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

e então assumir que

• nossa transação é bem-sucedida na terceira tentativa,
• porque na primeira tentativa ele é invalidado por outra transação simultânea sendo confirmada que altera o valor interno malogo após o término wa <- readTVar mada nossa transação,
• e na segunda tentativa ele é invalidado por outra transação simultânea que altera o conteúdo de uma ou ambas as transações mae mblogo depois writeTVar ma (Set.delete win wa)da nossa transação.

Como o log de transações evoluiria nesse caso e em que ponto a validação falharia?

O trecho relevante de Parallel and Concurrent Programming in Haskell de Simon Marlow está abaixo (mas informações semelhantes estão disponíveis no artigo Beautiful concurrency de Simon Peyton Jones):

Uma transação STM funciona acumulando um log de readTVaroperações writeTVarque ocorreram até o momento durante a transação. O log é usado de três maneiras:

• Ao armazenar writeTVaras operações no log em vez de aplicá-las imediatamente à memória principal, descartar os efeitos de uma transação é fácil; simplesmente descartamos o log. Portanto, abortar uma transação tem um custo fixo pequeno.

• Cada um readTVardeve percorrer o log para verificar se o TVarfoi escrito por um writeTVar. Portanto, readTVaré uma operação O(n) no comprimento do log.

• Como o log contém um registro de todas as readTVaroperações, ele pode ser usado para descobrir o conjunto completo de TVarsleituras durante a transação, o que precisamos saber para implementar retry.

Quando uma transação chega ao fim, a implementação do STM compara o log com o conteúdo da memória. Se o conteúdo atual da memória corresponder aos valores lidos por readTVar, os efeitos da transação são confirmados na memória; caso contrário, o log é descartado e a transação é executada novamente desde o início. Esse processo ocorre atomicamente, bloqueando todos os TVarsenvolvidos na transação durante sua duração. A implementação do STM no GHC não utiliza bloqueios globais; apenas os TVarsenvolvidos na transação são bloqueados durante o commit, de modo que transações que operam em conjuntos disjuntos de TVarspodem prosseguir sem interferência.

Em Programação Paralela e Concorrente em Haskell , de Simon Marlow, o capítulo 7 começa na página 125 com este exemplo,

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')

que tem uma saída como esta

BBBBBBBABABABAAAAAAA

(que, aliás, é o resultado que realmente obtive ao alterar 100000para 10o snippet acima e executar o programa).

No final do capítulo, página 140, é feito o seguinte comentário (grifo meu):

[…] Este é um exemplo da garantia de imparcialidade na prática. […]. Portanto, isso leva à alternância perfeita entre as duas threads. A única maneira de o padrão de alternância ser quebrado é se uma thread for desescalonada enquanto não estiver segurando o MVar. De fato, isso acontece de tempos em tempos como resultado da preempção, e ocasionalmente vemos uma longa sequência de uma única letra na saída.

Com base no resultado que mostrei, sim, consigo ver que a alternância está quebrada, mas não entendi bem a explicação acima. Não há nem um MVarno primeiro exemplo.

Em Programação Paralela e Concorrente em Haskell , de Simon Marlow, nas páginas 133 e 134, o seguinte código é mostrado:

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)

E na página seguinte, algumas observações. A parte final do segundo parágrafo me intriga um pouco. Aqui está a primeira metade do parágrafo:

Usar estruturas de dados imutáveis ​​em um wrapper mutável traz outros benefícios. Observe que, na lookupoperação, simplesmente capturamos o valor atual do estado e, em seguida, a Map.lookupoperação complexa ocorre fora da sequência takeMVar/ putMVar. Isso é bom para a concorrência, pois significa que o bloqueio é mantido apenas por um período muito curto.

Isso é bastante claro para mim, no sentido de que entendo que isso takeMVarcoloca o bloqueio e putMVaro libera imediatamente, de modo que os acessos simultâneos subsequentes ao PhoneBookStatenão sejam mais prejudicados. Ao mesmo tempo, também vejo que outras mutações do MVarsão possíveis, então, quando o tempo lookupretorna com um Just smth, esse (name, smth)par pode ter sido removido do mapa (ou, se retornou Nothing, alguns (name, smth)podem ter sido adicionados ao mapa).

Entretanto, não entendi o que a seguinte parte do parágrafo tenta transmitir:

Isso só é possível porque o valor do estado é imutável. Se a estrutura de dados fosse mutável, teríamos que manter o bloqueio enquanto operávamos nela.⁵

---

⁵. A outra opção é usar um algoritmo sem bloqueios, que é extremamente complexo e difícil de acertar.

O que isso significa? O autor está se referindo ao caso que Mapexpôs alguma API a uma mutação? Isso nem é possível, a menos que estejamos em IO, certo? Ou ele está se referindo a mutações realizadas no mconteúdo de (por outras threads após putMVara liberação do bloqueio) que de alguma forma afetaram booko conteúdo de ?

Não consegui encontrar documentação para esse comportamento e parece ser um bug ([Editar] de fato é: gitlab.haskell.org/ghc/ghc/-/issues/10387 ). Estou esquecendo de algo?

Em GHCi:

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

    > inf
    Infinity

    > infinity
    1 % 0

    > fromRational infinity
    Infinity

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

[Editar:]

Existe uma solução alternativa. Usando o pacote ieee754 , é possível definir o seguinte:

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))

Isso produz o erro:

 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

Usando cryptono pacote Haskell, estou tentando gerar a mesma saída, openssl dgstmas não consigo descobrir o que estou fazendo errado. Por favor, ajudem.

openssl dgst:

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

criptônio:

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

Obrigado.

Li que variáveis ​​são imutáveis ​​em Haskell e algo como o seguinte não funciona em Haskell.

x = 30
x = x+1

Mas ainda tentei isso para ver o que o compilador retorna e obtive o seguinte:

O compilador simplesmente para de responder e não faz nada até que eu pressione ctrl+c e o interrompa.

Por que isso acontece e por que o compilador deixa de responder em vez de me retornar algum tipo de erro?

Estou trabalhando com uma implementação Haskell de geradores para uma tarefa de casa. Tenho uma andAlsofunção que supostamente adiciona um predicado adicional a um gerador, mas não está funcionando corretamente em todos os casos de teste. Embora pareça correto

Aqui está minha definição de tipo de gerador:

-- 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)

Minha implementação atual de 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)

Estou usando uma função auxiliar takeGenpara visualizar os resultados dos testes:

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)

Casos de teste e resultados

Aqui estão meus casos de teste e seus resultados:

-- 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]

O que eu tentei

Eu tentei várias implementações de andAlso, incluindo:

1. A implementação atual mostrada acima
2. Ajustando como os predicados são aplicados na sequência
3. Tentando encontrar o primeiro valor válido que satisfaça ambos os predicados

Alguns casos de teste funcionam corretamente, mas outros (especificamente os testes 1 e 2) não retornam todos os valores esperados.

Minha pergunta

O que há de errado com minha andAlsoimplementação e como devo consertar para fazer todos os casos de teste funcionarem conforme o esperado? O problema é com a forma como o gerador é definido, como takeGenfunciona ou como andAlsoaplica o predicado adicional?

Contexto adicional

Outras funções relacionadas ao gerador que implementei:

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

Obrigado por qualquer ajuda para entender onde minha implementação está dando errado.

Uma biblioteca de análise sintática mínima absoluta poderia ser:

{- | 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

Isto compila (com linguagem GHC2021; tem que adicionar algumas importações). Carregando em ghci em cabal repl:

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

Isso significa que o analisador consumiu toda a entrada -- o que eu esperava ver era Right ("01", "23").

Então minha pergunta: onde a preguiça "quebra", por assim dizer, e há alguma maneira de restaurá-la? E por "restaurá-la" quero dizer fazer a implementação da instância de forma diferente para que manyseja tão preguiçosa quanto o esperado, porque se eu adicionar

{- | 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)

E carrego no ghci, obtenho o esperado:

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

Aqui está a definição da mônada de estado do capítulo 13 de Learn You a Haskell

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

Com base nessa definição, parece-me que o estado na tupla retornada por f aserá substituído por newStatemesmo que seja a versão mais recente. Para pegar um exemplo específico do capítulo 10 do Real World Haskell, onde isso claramente não é o que os autores pretendem (observe o uso de em vez de porque eles ainda não introduziram formalmente as mônadas)==>>>=

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

Onde

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

Em parseByte, não vejo como initStatenão substitui newState.