LINUX.ORG.RU

[haskell] гуру, прокомментируйте код плиз

 


0

0

Привет!

Вникаю в haskell по книге Real World Haskell, там встретилось такое задание - транспонировать текст в файле, т.е. файл с содержимым

transpose :: [Char] -> [Char]
transpose fc = let
	-- put additional spaces to the end of the string
	putSpaces s i | length s < i = putSpaces (s ++ " ") i
		      | otherwise = s

	-- transpose one string
	transStr (r:rs) (l:ls) cnt = [putSpaces r cnt ++ [l]] ++ transStr rs ls cnt
	transStr (r:rs) [] cnt = (r:rs)
	transStr [] (l:ls) cnt = [putSpaces [] cnt ++ [l]] ++ transStr [] ls cnt
	transStr [] [] cnt = []

	-- transpose all lines
	transLines rs ls cnt | not (null ls) = transLines (transStr rs (head ls) cnt) (tail ls) (cnt + 1)
		             | otherwise = (rs, ls)

	-- extract result from transLines tuple
	reportResult (rs, ls) = unlines rs

    in reportResult (transLines [] (lines fc) 0)

должен превратиться в

tt			 					 			 		  
rr-p	 -tttt -t	 -r  
aa-u  -rrrr -r  -e  
nn t   aaaa  a   p  
sspS  tnnnn tn  eo i
ppup  rssss rs  xr n
oota  aSSSS aL  tt  
ss c  ntttt ni  rR r
eeae| srrrr sn  ae e
  ds  p     pe  cs p
:fd o o(([[ os  tu o
:cist srr]] s    l r
  t h e::   er  rt t
[=iie  rr([  s  e  R
C o r ossl] a   s( e
hln|w n)):  ll| ur s
aea i e  lc ls  ls u
rtlls  ([sn   o t, l
]  ee sl])t lct    t
  sn  t:    inh fl  
- pg= rlcc= nte rs (

(поскипано, дальше в том же духе)

Собственно, в первом блоке кода - моё решение задачи. Вопрос такой - оптимальна ли реализация с точки зрения фп и ленивых вычислений? На том же Си можно было бы написать то же самое с меньшей сложностью алгоритма (особенно это касается добавления пробелов в конец строки, если она короче, чем надо). Но может быть, благодаря ленивым вычислениям это в достаточной мере соптимизируется? Если нет - как этот код можно сделать быстрее?

★★★

ну и кто тебе сказал, что в ФП пробелы по одному добавляют? :)

не соптимизируется ни разу, у тебя каждое добавление пробела это O(s), где s - длина строки

mholub
()
Ответ на: комментарий от mholub

я знаю :) потому и спрашиваю - как правильно.

shuthdar ★★★
() автор топика
Ответ на: комментарий от mholub

с другой стороны - эта функция на O(n) конструирует список из пробелов. насколько я понимаю, любая строка в хаскеле в любом случае является списком с соответствующими издержками на обработку.

shuthdar ★★★
() автор топика
Ответ на: комментарий от shuthdar

Что-то голова у меня мутная, да и не гуру я, но

transpose :: [Char] -> [Char]
transpose = unlines . transpose' . lines
  where transpose' ls | all null ls = []
	transpose' ls = map safeHead ls : transpose' (map safeTail ls)
        safeHead [] = ' '
        safeHead l = head l
	safeTail [] = []
	safeTail l = tail l 
mholub
()
Ответ на: комментарий от mholub

Работает. Только ключевые слова есть "незнакомые", которые как раз в следующей главе начинаются, пытался делать, не забегая вперёд :) Кстати, что значат точки в [code]unlines . transpose' . lines[/code]?

shuthdar ★★★
() автор топика
Ответ на: комментарий от shuthdar

Ну ты в принципе пока читай и практикуйся. Работает? работает! Значит первые главы усвоил. Сейчас познакомишься с функциями высшего порядка, а в частности со всеми этими map'ами, fold'ами, filter'ами и прочими полезными функциями и начнешь писать по-другому.

"точка" это композиция функций. (f . g) x = f (g x)

mholub
()
putSpaces s i | length s < i = putSpaces (s ++ " ") i
              | otherwise = s

Этот код неоптимален по нескольким причинам. 1) Каждый рекурсивный вызов ф-ции пересчитывает длинну входной строки. 2) Добавление по одному пробелу в конец строки неэффективно. И тут ленивость не поможет.

Такую ф-цию можно было-бы написать так:

putSpaces s i | l < i = s ++ replicate (i-l) ' '
              | otherwise = s
             where l = length s  
Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

2) Добавление по одному пробелу в конец строки неэффективно. И тут ленивость не поможет.

Бгг, может я что-то интересное не знаю о ленивости? Объясни, пожалуйста, почему это не поможет. Код (++) в помощь: http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-Base.html#%2B%2B

balodja ★★★
()

Посмотри онлайновую версию книги http://book.realworldhaskell.org/read/ Там возле каждого упражения есть ссылки на комментарии с обсуждением и несколькими решениями. )

ipc
()
Ответ на: комментарий от balodja

>Бгг, может я что-то интересное не знаю о ленивости? Объясни, пожалуйста, почему это не поможет. Код (++) в помощь:
Там length после каждого пробела вызывается. То есть список полный будет строится для каждого пробела. Или я неправ?

ratatosk
()
Ответ на: комментарий от balodja

Бгг, может я что-то интересное не знаю о ленивости? Объясни, пожалуйста, почему это не поможет. Код (++) в помощь: http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-Base.html#++

Потому, что (++) будет вызываться не в том порядке, котором хотелось бы. Правильно:

"123" ++ (" " ++ (" " ++ ...))
Мы же имеем:
(..((("123" ++ " ") ++ " ") ++ " ") ++ ..

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Да, в этом есть резон. Действительно не поможет.

balodja ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.