Agda: чтение строки стандартного ввода в виде строки вместо строки затрат

Question

Я пытаюсь написать простую программу, которая читает строку из стандартного ввода, переворачивает ее, а затем печатает перевернутую строку.

К сожалению родной getLine функция читает Costring; Я могу только повернуть вспять Strings; и нет функции, которая принимает Costring к String,

Как я могу изменить эту программу для компиляции?

module EchoInputReverse where

-- Agda standard library 0.7
open import Data.List using (reverse)
open import Data.String
open import Foreign.Haskell using (Unit)
open import IO.Primitive

postulate
  getLine : IO Costring

{-# COMPILED getLine getLine #-}

main : IO Unit
main = 
  getLine >>= (λ s → 
  -- NOTE: Need a (toString : Costring → String) here. Or some other strategy.
  return (toCostring (fromList (reverse (toList (toString s))))) >>= (λ s' → 
  putStrLn s'))

Answer 1

Вы не можете сделать это, по крайней мере, не напрямую. Проблема в том, что Costring может быть бесконечным по размеру, в то время как Strings должно быть конечным.

Представьте себе запуск программы как prog < /dev/zeroчто должно произойти? reverse Функция может создать первый элемент только после достижения конца списка ввода, и это может никогда не произойти.

Нам нужно выразить тот факт, что преобразование Costring в String может потерпеть неудачу. Один из способов сделать это - использовать монаду пристрастности. Давайте посмотрим на определение:

data _⊥ {a} (A : Set a) : Set a where
  now   : (x : A) → A ⊥
  later : (x : ∞ (A ⊥)) → A ⊥

Таким образом, мы можем иметь значение типа A право nowили нам нужно ждать later, Но обратите внимание на ∞ символ: это означает, что мы можем на самом деле ждать вечно (так как может быть бесконечное количество later Конструкторы).

Я объединю преобразование и обращение в одну функцию. Импортирует сначала:

open import Category.Monad.Partiality
open import Coinduction
open import Data.Char
open import Data.Colist
  using ([]; _∷_)
open import Data.List
  using ([]; _∷_; List)
open import Data.String
open import Data.Unit
open import IO

Теперь тип нашего reverse Функция должна упомянуть, что мы берем Costring в качестве входных данных, но и возвращая String может потерпеть неудачу. Реализация тогда довольно проста, это обычный обратный процесс с аккумулятором:

reverse : Costring → String ⊥
reverse = go []
  where
  go : List Char → Costring → String ⊥
  go acc []       = now (fromList acc)
  go acc (x ∷ xs) = later (♯ go (x ∷ acc) (♭ xs))

Тем не менее, мы можем напечатать String, но нет String ⊥! Это где IO помогает: мы можем интерпретировать later конструкторы, как "ничего не делать", и если мы найдем now конструктор, мы можем putStrLn String это содержит.

putStrLn⊥ : String ⊥ → IO ⊤
putStrLn⊥ (now   s) = putStrLn s
putStrLn⊥ (later s) = ♯ return tt >> ♯ putStrLn⊥ (♭ s)

Обратите внимание, что я использую IO от IO модуль, а не тот из IO.Primitive, Это в основном слой, построенный на постулатах, так что это немного лучше. Но если вы хотите использовать getLine с этим вы должны написать:

import IO.Primitive as Prim

postulate
  primGetLine : Prim.IO Costring

{-# COMPILED primGetLine getLine #-}

getLine : IO Costring
getLine = lift primGetLine

И, наконец, мы можем написать main функция:

main = run (♯ getLine >>= λ c → ♯ putStrLn⊥ (reverse c))

---

Компиляция этой программы с использованием C-c C-x C-c и затем, запустив его, мы получаем ожидаемое:

$ cat test
hello world
$ prog < test    
dlrow olleh

Answer 2

Сайзан на #agda указывает, что можно просто постулировать, что getLine : IO String вместо getLine : IO Costring, Это работает. Итак, вы получите:

module EchoInputReverse where

-- Agda standard library 0.7
open import Data.List using (reverse)
open import Data.String
open import Foreign.Haskell using (Unit)
open import IO.Primitive

postulate
  getLine : IO String

{-# COMPILED getLine getLine #-}

main : IO Unit
main = 
  getLine >>= (λ s → 
  return (toCostring (fromList (reverse (toList s)))) >>= (λ s' → 
  putStrLn s'))

---

Недостатком является то, что этот подход утверждает, что getLine всегда возвращает конечную строку, которая может быть неправильной в случае prog < /dev/zero как указывает @Vitus.

Но я не думаю, что это имеет значение. Если getLine действительно возвращает бесконечную строку, тогда ни это решение, ни решение @ Vitus не приведут к завершению программы. У них такое же поведение.

Было бы идеально определить, был ли вход бесконечным, и в этом случае выдать ошибку. Но этот тип обнаружения бесконечности на IO вообще невозможен.