[haskell]問個求子串位置的程序

retuor

做了個練習，大家給點意見。

Exercise 10. Write a function         f :: String -> String -> Maybe Int
that takes two strings. If the second string appears within the first, it
returns the index identifying where it starts. Indexes start from 0. For
example,
         f "abcde" "bc" ==> Just 1
         f "abcde" "fg" ==> Nothing

我的想法是，如果 s2 是 s1=(x:xs) 的前綴，則返回 0，否則返回 1+ s2 在 xs 中的位置，如是遞歸下去。由于題目要求返回 Maybe 類型，最好能有  (Just 1)+(Just 1)=Just 2 之類的運算，所以寫了個 Maybe Int 的 instance.

1. 
   
2. instance (Num a)=> Num (Maybe a) where
   
3.     (Just n) + (Just m) = Just (n+m)
   
4.     _+_=Nothing                          
   
5. 
   
6. f [] s2=Nothing
   
7. f s1@(x:xs) s2 = if isPrefix s1 s2 then Just 0 else (Just 1)+ (f xs s2)
   
8.                  where
   
9.                    isPrefix _ [] = True
   
10.                    isPrefix (x:xs) (y:ys) = if x==y then isPrefix xs ys else False
    
11.                    isPrefix _ _ = False
    

復(fù)制代碼

SNYH

1. 
   
2. else (Just 1)+ (f xs s2)
   
3. 可以改為
   
4. else  fmap (+1) (f xs s2)
   
5. 不需要instance
   
6. Maybe 是一個典型的functor
   

復(fù)制代碼

而且你實現(xiàn)的這個Num 的instance 不完全其他的幾個方法沒有實現(xiàn)會出現(xiàn)警告的


另外 isPrefix 在Data.List 中有一個對應(yīng)的函數(shù)  Data.List.isPrefixOf

SNYH

再補充點
isPrefix s1 s2
一般如果是這種名字的函數(shù)寫成
  s1 `isPrefix` s2  可讀性是不是強點？

retuor

fmap 好，改過來了。

1. 
   
2. f [] s2=Nothing
   
3. f s1@(x:xs) s2 = if isPrefix s1 s2 then Just 0 else fmap (+1) (f xs s2)
   
4.                  where
   
5.                    isPrefix _ [] = True
   
6.                    isPrefix (x:xs) (y:ys) = if x==y then isPrefix xs ys else False
   
7.                    isPrefix _ _ = False
   

復(fù)制代碼

可讀性那個也很有道理，不過暫時不改了。

有收獲，謝謝啊。

SNYH

[code]fmap (+1) (f xs s2) [\code]
換成
[code]f xs s2 >>= (\x -> return (x+1))[\code]
也是差不多


一個用的functor  一個用的是monad

還可以直接使用 pattern match
比如寫個
maybeAdd Nothing _ = Nothing
maybeAdd _ Nothing = Nothing
maybeAdd (Just x) (Just y) = Just (x+y)

helper function 相對來說也比 實現(xiàn) 一個  instance 來實現(xiàn)(+)要好點吧。。。。

retuor

嘿嘿，再次學到，

1. 
   
2. f [] s2=Nothing
   
3. f s1@(x:xs) s2 = if isPrefix s1 s2 then Just 0 else (f xs s2)>>=return.(+1)
   
4.                  where
   
5.                    isPrefix _ [] = True
   
6.                    isPrefix (x:xs) (y:ys) = if x==y then isPrefix xs ys else False
   
7.                    isPrefix _ _ = False
   

復(fù)制代碼